Linked List Cycle

Q: מהי סיבוכיות הזמן והמקום של Linked List Cycle?

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

Q: למה המצביע המהיר לא יכול לדלג מעל המצביע האיטי?

בתוך המחזור, בכל סיבוב fast מתקדם בשני צמתים ו־ slow בצומת אחד, ולכן המרחק ש־ fast עדיין צריך לעבור כדי להגיע אל slow קטן בדיוק באחד. מרחק שיורד באחד בכל סיבוב הוא 3, 2, 1, 0 ואינו יכול לעבור מתחת לאפס, ולכן שני המצביעים נפגשים בצומת.

Q: האם תוכל לזהות את המחזור על ידי ספירת הצעדים?

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

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

+10

רשימה מקושרת מאוחסנת במערך next: הצומת i מקושר לצומת next[i], ו--1 מציין שהרשימה מסתיימת שם. הראש הוא הצומת 0. עקבו אחר הקישורים מהראש והחזירו true אם חוזרים אי פעם לצומת שכבר ביקרתם בו, או false אם מגיעים לסוף. צמתים שהמעבר לא מגיע אליהם אינם נחשבים, גם אם הם מקושרים זה לזה בלולאה.

פונקציה

hasCycle(next: integer-array) → boolean

nextinteger-array: הקישור של כל צומת: next[i] הוא הצומת שאחרי צומת i, או ‎-1
מחזירהboolean: ‏true אם המסלול מהצומת 0 מבקר שוב בצומת, ‏false אם הוא מגיע ל־-1

אילוצים

1 ≤ next.length ≤ 10⁴
-1 ≤ next[i] ≤ next.length-1
כמה צמתים עשויים לקשר לאותו צומת, וייתכן שחלק מהצמתים אינם ניתנים להגעה מהראש.

דוגמאות

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

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

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

+16 בדיקות נסתרות בשליחה

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

סמן את הצמתים שבהם אתה מבקר

האינטואיציה

התחילו ללכת מהצומת 0 וסמנו כל צומת כשאתם עוזבים אותו. אם אתם מגיעים לצומת שכבר סומן, ההליכה חזרה אליו, ומשם היא חוזרת על עצמה לנצח: זהו מעגל. בדוגמה 1 אתם מסמנים את 0, 1, 2 ו-3, והקישור מהצומת 3 מוביל לצומת 1, שכבר סומן.

הצמתים ממוספרים מ-0 עד n-1, ולכן מערך בוליאני באורך n משמש כקבוצת הצמתים שבהם כבר ביקרנו. ברשימה מקושרת שנבנתה מאובייקטים, הייתם מכניסים את ההפניות לצמתים לקבוצת גיבוב במקום זאת; הרעיון זהה.

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

אלגוריתם

צרו מערך בוליאני visited באורך n, שכל הערכים בו הם false.
הגדירו node = 0.
כל עוד node אינו -1, החזירו true אם visited[node] כבר true.
אחרת, הגדירו את visited[node] ועברו אל next[node].
כשההליכה מגיעה אל -1, החזירו false.

def hasCycle(next):
    visited = [False] * len(next)
    node = 0
    while node != -1:
        if visited[node]:
            return True  # back at a node already on the path
        visited[node] = True
        node = next[node]
    return False

מצביעים מהירים ואיטיים (זיהוי מחזור של פלויד)

האינטואיציה

התחילו שני מצביעים בראש הרשימה. slow מתקדם קישור אחד בכל סיבוב ו-fast מתקדם שני קישורים. אם הרשימה מסתיימת, fast מגיע ל--1 ראשון ומחזירים false. אם יש מחזור, fast נכנס אליו ראשון וממשיך להקיף אותו עד שגם slow מגיע אליו.

ברגע ששניהם בתוך המחזור, בכל סיבוב fast מתקדם בדיוק צומת אחד יותר מ-slow. המרחק ש-fast עדיין צריך לעבור כדי להגיע ל-slow קטן באחד בכל סיבוב, ולכן הוא מגיע לאפס והמצביעים נוחתים על אותו צומת. מכיוון ש-fast מתקדם צומת אחד בכל פעם, הוא לעולם לא יכול לדלג מעל slow.

בדוגמה 1, אחרי סיבוב אחד slow נמצא בצומת 1 ו-fast בצומת 2. אחרי שני סיבובים slow נמצא בצומת 2 ו-fast עבר דרך 3, 1. אחרי שלושה סיבובים שניהם נמצאים בצומת 3, ולכן התשובה היא true.

ל-slow נדרשים לכל היותר n סיבובים כדי להיכנס למחזור, וברגע שהוא בפנים הם נפגשים לפני שהוא מסיים הקפה אחת, ולכן זמן הריצה הוא O(n). הזיכרון היחיד שנדרש הוא שני מספרי צמתים.

אלגוריתם

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

def hasCycle(next):
    slow = 0
    fast = 0
    # fast needs two links to move; if either is missing, the list ends.
    while fast != -1 and next[fast] != -1:
        slow = next[slow]
        fast = next[next[fast]]
        if slow == fast:
            return True
    return False

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

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

הזזה של fast בשני קישורים בלי לבדוק את שניהם. גם fast וגם next[fast] חייבים להיות צמתים קיימים לפני שקוראים את next[next[fast]]; אחרת קוראים את next[-1], מה שגורם לקריסה ברוב השפות ומחזיר בשקט את האיבר האחרון ב-Python.
השוואת המצביעים לפני שמזיזים אותם. שניהם מתחילים בצומת 0, ולכן בדיקה בתחילת הלולאה מדווחת על מעגל בכל רשימה.
בדיקת המערך כולו במקום המסלול. ב-[-1, 2, 1] הצמתים 1 ו-2 יוצרים לולאה, אבל המסלול מהראש מסתיים מיד, ולכן התשובה היא false. גם בדיקה אם ערך חוזר ב-next היא שגויה: ב-[4, 4, 4, 4, -1] כמה צמתים מקושרים לצומת 4 ואין מעגל.
הנחה שמעגל חייב לחזור לראש. ב-[1, 2, 3, 4, 4] הצומת האחרון מקושר לעצמו, וגם ב-[0] הראש מקושר לעצמו.

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

איך פועלת זיהוי מחזורים של Floyd?

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

מהי סיבוכיות הזמן והמקום של Linked List Cycle?

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

למה המצביע המהיר לא יכול לדלג מעל המצביע האיטי?

בתוך המחזור, בכל סיבוב fast מתקדם בשני צמתים ו־slow בצומת אחד, ולכן המרחק ש־fast עדיין צריך לעבור כדי להגיע אל slow קטן בדיוק באחד. מרחק שיורד באחד בכל סיבוב הוא 3, 2, 1, 0 ואינו יכול לעבור מתחת לאפס, ולכן שני המצביעים נפגשים בצומת.

האם תוכל לזהות את המחזור על ידי ספירת הצעדים?

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

Python

def hasCycle(next):
    # כתבו כאן קוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

next = [1, 2, 3, 1]

צפוי

true