Palindrome Linked List

Q: מהי סיבוכיות הזמן של בדיקת רשימה מקושרת פלינדרומית?

כל גישה היא O(L) עבור רשימה של L צמתים, כי צריך להשוות כל ערך. העתקת הערכים למערך או למחסנית צורכת זיכרון נוסף בגודל O(L) ; היפוך המחצית השנייה במקום צורך O(1) .

Q: איך המצביע המהיר והמצביע האיטי מוצאים את האמצע של רשימה מקושרת?

שניהם מתחילים בראש, והמצביע המהיר מתקדם שני צעדים על כל צעד של המצביע האיטי. כשהמצביע המהיר מגיע לסוף, הוא עבר על כל הרשימה, והמצביע האיטי עבר על מחציתה.

Q: האם היפוך של חצי מהרשימה הורס את הקלט?

כן, זה משנה את הקישורים של החצי השני, וברוב השפות המערך הזה שייך למי שקרא לפונקציה. אם עדיין צריך את הרשימה, סיים את ההשוואה בלי להחזיר מוקדם, ואז הפוך שוב את החצי הזה. הצומת האמצעי עדיין מקושר לצומת הראשון של החצי, כך שהרשימה שוב שלמה, עם זיכרון נוסף של O(1) .

קלרשימה מקושרת מצביע מהיר ואיטי שני מצביעים

+10

ניתנת לך רשימה מקושרת חד־כיוונית השמורה בשני מערכים באותו אורך. הצומת i מכיל את הערך values[i] ומקושר לצומת next[i], הערך -1 מסמן את סוף הרשימה, והראש הוא הצומת 0. הצמתים אינם מאוחסנים לפי סדר הרשימה, לכן יש לעקוב אחר הקישורים.

החזר true אם הערכים שנקראים מהראש ועד הסוף זהים לערכים שנקראים מהסוף בחזרה לראש, ו-false אחרת.

פונקציה

isPalindrome(next: integer-array, values: integer-array) → boolean

nextinteger-array: האינדקס של הצומת שאליו כל צומת מקשר, או -1 עבור הצומת האחרון
valuesinteger-array: הערך שמוחזק בכל צומת
מחזירהboolean: true אם הרשימה נקראת אותו הדבר בשני הכיוונים

אילוצים

1 ≤ L ≤ 5000, כאשר L הוא האורך של next ושל values.
-100 ≤ values[i] ≤ 100
כל next[i] הוא -1 או אינדקס של צומת מ־0 עד L-1.
החל מהצומת 0, הרשימה עוברת בכל צומת פעם אחת בדיוק ואז מגיעה אל -1. אין מעגל.

דוגמאות

קלט: next = [4, 3, -1, 2, 1]values = [3, 4, 3, 1, 1]
פלט: true
הסבר: הקישורים מבקרים בצמתים 0, 4, 1, 3, 2, ולכן הרשימה היא 3, 1, 4, 1, 3. שני ה־3 תואמים, שני ה־1 תואמים, ול־4 שבאמצע אין בן זוג להשוואה.

קלט: next = [2, -1, 3, 1]values = [4, 4, 9, 9]
פלט: true
הסבר: הרשימה עוברת בצמתים 0, 2, 3, 1 וקוראת 4, 9, 9, 4, אותו הדבר בשני הכיוונים.

קלט: next = [2, -1, 1]values = [1, 2, 1]
פלט: false
הסבר: המערך values הוא [1, 2, 1], אבל הרשימה מבקרת בצמתים 0, 2, 1 וקוראת 1, 1, 2. בכיוון ההפוך זה 2, 1, 1, ולכן התשובה היא false.

שאלת המשך

האם אפשר לעשות זאת בזמן O(L) ובשימוש בזיכרון נוסף של O(1)?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

בדיקת פלינדרום משווה כל ערך לערך התואם לו בקצה השני. רשימה מקושרת חד־כיוונית עוברת רק קדימה, ולכן החלק הקשה הוא לקרוא את החצי השני בסדר הפוך. העתקה למערך עושה זאת תוך שימוש בזיכרון של O(L), כאשר L הוא מספר הצמתים; היפוך הקישורים בחצי השני עושה זאת תוך שימוש בזיכרון של O(1).

העתק את הערכים למערך

האינטואיציה

מצביע כאן הוא אינדקס של צומת, והתקדמות קדימה נעשית באמצעות node = next[node]. עוברים על הרשימה פעם אחת ומעתיקים כל ערך למערך, שאפשר לקרוא ממנו משני הקצוות. משווים בין הערך הראשון לאחרון, מזיזים את שני האינדקסים לכיוון האמצע ומחזירים false אם יש אי-התאמה כלשהי. באורך אי-זוגי, הערך האמצעי הוא בן הזוג של עצמו.

צריך לקרוא כל ערך, ולכן זמן הריצה O(L) הוא הטוב ביותר האפשרי. העלות היא L מספרים שלמים נוספים.

אלגוריתם

עבור מהצומת 0 עד -1 והוסף כל values[node] למערך.
הגדר i = 0 ואת j לאינדקס האחרון.
כל עוד i < j, החזר false אם שני הערכים שונים, אחרת הגדל את i והקטן את j.
החזר true.

def isPalindrome(next, values):
    # Write the values out in list order.
    seq = []
    node = 0
    while node != -1:
        seq.append(values[node])
        node = next[node]
    # Compare from both ends toward the middle.
    i = 0
    j = len(seq) - 1
    while i < j:
        if seq[i] != seq[j]:
            return False
        i += 1
        j -= 1
    return True

הפוך את החצי השני במקומו

האינטואיציה

הפוך את הקישורים של החצי האחורי במקום להעתיק אותו: הליכה מהצומת האחרון הישן מובילה אז לכיוון האמצע. כדי למצוא את האמצע, הזז את fast שני קישורים על כל קישור ש-slow זז, כל עוד יש ל-fast שני קישורים לפניו. slow נעצר בצומת האחרון של החצי הראשון, בצומת האמצעי כאשר L אי-זוגי. בדוגמה הראשונה slow עובר 0 → 4 → 1 בעוד fast עובר 0 → 1 → 2, ולכן slow נעצר על 4.

הפוך את הצמתים שאחרי slow, ואז התקדם יחד עם left מראש הרשימה ועם right מהחצי ההפוך: 3 מול 3, ואז 1 מול 1. החצי ההפוך לעולם אינו ארוך יותר מהחצי הראשון, לכן עצירה כש-right מסתיים משווה בדיוק את הזוגות החשובים. כל שלב עובר על לכל היותר L צמתים ושומר כמה מספרים שלמים. ב-R, שינוי next_ מעתיק את הווקטור פעם אחת, ולכן R משתמש ב-O(L) זיכרון.

אלגוריתם

אתחל את slow = fast = 0. כל עוד next[fast] וגם next[next[fast]] אינם -1, קדם את slow בקישור אחד ואת fast בשני קישורים.
הפוך את הרשימה שמתחילה ב־next[slow]: עבור כל צומת, שמור את הקישור שלו, הפנה אותו אל prev, ואז קדם את prev ואת הצומת.
הגדר left = 0 ואת right = prev, ראש החצי ההפוך.
כל עוד right != -1, החזר false במקרה של אי־התאמה, אחרת קדם את שני המצביעים בקישור אחד.
החזר true.

def isPalindrome(next, values):
    # Find the middle: fast moves two links for every one link slow moves.
    slow = 0
    fast = 0
    while next[fast] != -1 and next[next[fast]] != -1:
        slow = next[slow]
        fast = next[next[fast]]
    # slow is the last node of the first half (the middle node when the length is odd).
    # Reverse the links of the second half.
    prev = -1
    node = next[slow]
    while node != -1:
        after = next[node]
        next[node] = prev
        prev = node
        node = after
    # prev is the old last node, now the head of the reversed half.
    left = 0
    right = prev
    while right != -1:
        if values[left] != values[right]:
            return False
        left = next[left]
        right = next[right]
    return True

מלכודות ומקרי קצה

בדיקת המערכים במקום הרשימה. בדוגמה השלישית values הוא [1, 2, 1], אבל הרשימה היא 1, 1, 2.
בדיקה של next[fast] != -1 בלבד. לאחר מכן fast יכול לקפוץ אל -1 ולקרוא את next[-1], שנמצא מחוץ לטווח ברוב השפות, וב-Python וב-Ruby הוא מציין בשקט את האיבר האחרון.
השוואה עד ש-left מסתיים במקום עד ש-right מסתיים. הצומת האמצעי עדיין מקושר לחצי השני הישן, ולכן המעבר מהראש ארוך יותר.
דריסת next[node] במהלך ההיפוך לפני ששומרים אותו, מה שגורם לאובדן שאר הרשימה.
ב-Lua וב-R, שבהן מערכים מתחילים ב-1, קריאת next[node] עבור מזהה צומת שמתחיל מ-0. קראו את next[node + 1].

שאלות נפוצות3

מהי סיבוכיות הזמן של בדיקת רשימה מקושרת פלינדרומית?

כל גישה היא O(L) עבור רשימה של L צמתים, כי צריך להשוות כל ערך. העתקת הערכים למערך או למחסנית צורכת זיכרון נוסף בגודל O(L); היפוך המחצית השנייה במקום צורך O(1).

איך המצביע המהיר והמצביע האיטי מוצאים את האמצע של רשימה מקושרת?

שניהם מתחילים בראש, והמצביע המהיר מתקדם שני צעדים על כל צעד של המצביע האיטי. כשהמצביע המהיר מגיע לסוף, הוא עבר על כל הרשימה, והמצביע האיטי עבר על מחציתה.

האם היפוך של חצי מהרשימה הורס את הקלט?

כן, זה משנה את הקישורים של החצי השני, וברוב השפות המערך הזה שייך למי שקרא לפונקציה. אם עדיין צריך את הרשימה, סיים את ההשוואה בלי להחזיר מוקדם, ואז הפוך שוב את החצי הזה. הצומת האמצעי עדיין מקושר לצומת הראשון של החצי, כך שהרשימה שוב שלמה, עם זיכרון נוסף של O(1).

def isPalindrome(next, values):
    # כתבו כאן את הקוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

next = [4, 3, -1, 2, 1]
values = [3, 4, 3, 1, 1]

הפלט הצפוי

true