Intersection of Two Linked Lists
שתי רשימות מקושרות חד־כיווניות נמצאות באותו מאגר צמתים. צומת i מצביע לצומת next[i], ו--1 מסיים רשימה. רשימה A מתחילה בצומת headA ורשימה B בצומת headB. הצמתים מאוחסנים ללא סדר מסוים, ולכן יש לעקוב אחר הקישורים.
ייתכן ששתי הרשימות יתמזגו: החל מצומת מסוים, הן ממשיכות דרך אותם צמתים עד הסוף. יש להחזיר את האינדקס של הצומת הראשון שנמצא בשתי הרשימות, או -1 אם אין להן צומת משותף.
פונקציה
- nextinteger-array
- האינדקס של הצומת שאליו כל צומת מקשר, או -1 עבור הצומת האחרון ברשימה
- headAinteger
- הצומת הראשון ברשימה A
- headBinteger
- הצומת הראשון ברשימה B
- מחזירהinteger
- הצומת הראשון המשותף לשתי הרשימות, או -1
אילוצים
2 ≤ n ≤ 104, כאשרnהוא האורך שלnext.- כל
next[i]הוא-1או אינדקס של צומת מ־0עדn-1. 0 ≤ headA, headB ≤ n-1וגםheadA ≠ headB.- שתי הרשימות מסתיימות ב־
-1בלי לבקר בצומת פעמיים. אין מעגל. - כל צומת נמצא ברשימה A, ברשימה B או בשתיהן.
דוגמאות
- קלט
- next = [-1, 4, 1, 5, 0, 1]headA = 3headB = 2
- פלט
- 1
- הסבר
- A מבקר ב־
3, 5, 1, 4, 0ו־B מבקר ב־2, 1, 4, 0. החל מצומת1הם חולקים כל צומת, ואף צומת מוקדם יותר של A אינו נמצא ב־B, לכן התשובה היא1.
- קלט
- next = [2, 3, 4, -1, -1]headA = 0headB = 1
- פלט
- -1
- הסבר
- רשימה A היא
0, 2, 4ורשימה B היא1, 3. שתיהן מסתיימות ב־-1בלי להגיע לצומת משותף, ולכן התשובה היא-1.
- קלט
- next = [3, 2, 0, -1]headA = 1headB = 0
- פלט
- 0
- הסבר
- רשימה A היא
1, 2, 0, 3ורשימה B היא0, 3. רשימה B היא הזנב של רשימה A, ולכן הצומת המשותף הראשון הואheadBעצמו, הצומת0.
שאלת המשך
האם תוכל למצוא את הצומת בזמן O(m + k) ובזיכרון נוסף של O(1)?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
לצומת יש
nextאחד. ברגע ששתי הרשימות מגיעות לאותו צומת, האם הן יכולות להתפצל שוב? מה זה אומר לך על המבנה של שתי הרשימות?אם לשתי הרשימות היה אותו אורך, היית יכול לעבור עליהן זו לצד זו ולעצור כששני המצביעים עומדים על אותו צומת. הבעיה היא הצמתים הנוספים בתחילת הרשימה הארוכה יותר. איך שני המצביעים יכולים לעבור את אותו מרחק כולל?
הזז את המצביע
aלאורך רשימה A, וכשהוא מגיע לסופה, התחל אותו מחדש ב-headB. עשה אותו הדבר עבורb, והתחל אותו מחדש ב-headA. עצור כאשרa == b. הצומת הזה, או-1, הוא התשובה.
פתרון
לצומת יש next אחד, ולכן שתי רשימות שנפגשות לעולם לא מתפצלות שוב. הן יוצרות Y: שתי התחלות נפרדות שמתחברות לזנב משותף, והתשובה היא נקודת החיבור. ההתחלות יכולות להיות באורכים שונים, ולכן התקדמות בשתי הרשימות יחד מפספסת את נקודת החיבור. בהמשך, m ו-k הם האורכים של A ושל B.
בדוק כל צומת ב-A מול כל הצמתים ב-B
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
מצביע הוא אינדקס של צומת, והתקדמות קדימה היא node = next[node]. עבור כל צומת a של A לפי הסדר, עוברים על כל הצמתים של B ומשווים כל צומת ל-a. ה-a הראשון שמתאים הוא התשובה, כי כל צומת קודם של A כבר נכשל. סורקים מחדש את B עבור כל צומת של A: עם 5000 צמתים בכל רשימה וללא צומת משותף, מדובר ב-2.5 × 10^7 השוואות.
אלגוריתם
- קבע את
a = headA. - כל עוד
aאינו-1, עבור עםbמ־headBעד-1. - אם
b == aבשלב כלשהו, החזר אתa. - אחרת, העבר את
a = next[a]וחזור על הפעולה. - אם נגמרת רשימה A, החזר
-1.
def getIntersectionNode(next, headA, headB):
a = headA
while a != -1:
# Is node a also on list B? Walk all of B to find out.
b = headB
while b != -1:
if a == b:
return a
b = next[b]
a = next[a]
return -1סמן את הצמתים של רשימה B
האינטואיציה
ענה על השאלה "האם הצומת הזה נמצא ב-B?" פעם אחת עבור כל צומת: עבור לאורך B וסמן כל צומת במערך בוליאני בגודל n. אינדקסי הצמתים הם מספרים שלמים קטנים, ולכן מערך עושה את העבודה של קבוצת גיבוב. לאחר מכן עבור לאורך A מהראש שלו. הצומת המסומן הראשון נמצא בשתי הרשימות, והוא הצומת הראשון כזה כי אתה עובר לאורך A לפי הסדר. בדוגמה הראשונה B מסמן את 2, 1, 4, 0, והמעבר לאורך A עובר דרך 3 ו-5 לפני שהוא נעצר על 1. עוברים על כל רשימה פעם אחת, ולכן זמן הריצה הוא O(m + k), במחיר של n סימונים.
אלגוריתם
- צרו את
onB, מערך שלnערכים בוליאניים שמוגדרים כ-false. - עברו על רשימה B החל מ-
headBוהגדירוonB[node] = trueעבור כל צומת. - עברו על רשימה A החל מ-
headA. החזירו את הצומת הראשון שעבורוonB[node]הוא true. - אם רשימה A מסתיימת, החזירו
-1.
def getIntersectionNode(next, headA, headB):
# Mark every node of list B.
on_b = [False] * len(next)
node = headB
while node != -1:
on_b[node] = True
node = next[node]
# The first marked node on list A is the meeting point.
node = headA
while node != -1:
if on_b[node]:
return node
node = next[node]
return -1שני מצביעים שמחליפים בין רשימות
האינטואיציה
פצלו כל רשימה בנקודת החיבור: ל־A יש x צמתים פרטיים ואז את c הצמתים המשותפים, ול־B יש y צמתים פרטיים ואז את אותם c צמתים. המצביע a עובר לאורך A, מתקדם אל -1, ואז מתחיל מחדש מ־headB, ומגיע לנקודת החיבור בפעם השנייה אחרי x + c + 1 + y צעדים. המצביע b עובר לאורך B ואז לאורך A, ומגיע אחרי y + c + 1 + x צעדים. הסכומים שווים. בדוגמה הראשונה x = 2, y = 1 ו־c = 3, ושניהם עומדים על הצומת 1 אחרי שבעה צעדים.
כשאין זנב משותף, שני המצביעים עומדים על -1 אחרי m + 1 + k צעדים (אחרי m צעדים כאשר m = k), והלולאה מחזירה -1. העצירה המשותפת הזאת היא הסיבה לכך שכל מצביע מתקדם אל -1 לפני שהוא עובר לרשימה השנייה. כל מצביע מתקדם לכל היותר m + k + 1 פעמים, עם שני אינדקסים של זיכרון.
אלגוריתם
- הגדר את
a = headAואתb = headB. - כל עוד
a != b: העבר אתaאלheadBאם הוא-1, אחרת אלnext[a]. - באותו סבב, העבר את
bאלheadAאם הוא-1, אחרת אלnext[b]. - כשהלולאה מסתיימת, החזר את
a. זהו הצומת המשותף הראשון, או-1.
def getIntersectionNode(next, headA, headB):
a, b = headA, headB
# Each pointer walks its own list, then the other one. Both cover
# the same number of nodes, so they reach the meeting node together,
# or reach -1 together when there is none.
while a != b:
a = headB if a == -1 else next[a]
b = headA if b == -1 else next[b]
return a
מלכודות ומקרי קצה
- מעבר מהצומת האחרון ישר לראש השני, תוך דילוג על העצירה ב-
-1. כשהרשימות אינן חולקות צמתים, המצביעים לעולם אינם מחזיקים באותו ערך והלולאה פועלת לנצח. - אתחול מחדש של מצביע בראש הרשימה שלו. כל מצביע מקיף אז את הרשימה שלו, והם נפגשים רק כשההקפות מסתנכרנות, דבר שעשוי להימשך עד
(m + 1)·(k + 1)צעדים. - התייחסות לסדר המערך כאל סדר הרשימה. צומת
0הוא ראש רק אםheadAאוheadBמציינים זאת, וצמתים סמוכים במערך אינם צמתים סמוכים ברשימה. - ב-Lua וב-R, שכחה שמערכים מתחילים ב-1. השאירו את אינדקסי הצמתים מבוססי-0 וקראו את
next[node + 1].
שאלות נפוצות3
איך מוצאים היכן שתי רשימות מקושרות מצטלבות בלי להשתמש בזיכרון נוסף?
הפעל שני מצביעים. כל אחד מהם עובר על הרשימה שלו, ולאחר שהוא יוצא מקצה הרשימה, ממשיך מראש הרשימה השנייה. שניהם עוברים את אותו המרחק הכולל, ולכן מגיעים לצומת המשותף הראשון באותו הזמן, או מגיעים יחד לסוף אם אין צומת משותף.
האם תוכל למצוא את החיתוך על ידי השוואת אורכי הרשימות?
כן. סופרים את הצמתים בשתי הרשימות, מקדמים את המצביע ברשימה הארוכה יותר במספר הצמתים שבין אורכי הרשימות, ואז מקדמים את שניהם צעד אחד בכל פעם עד שהם שווים. גם השיטה הזו דורשת זמן O(m + k) וזיכרון O(1); שיטת ההחלפה משיגה את אותו יישור בלי שתי פעולות הספירה.
מהי סיבוכיות הזמן של מציאת החיתוך בין שתי רשימות מקושרות?
שתי השיטות של מצביע ואורך פועלות בזמן O(m + k) ודורשות זיכרון נוסף של O(1). זכירת רשימה אחת בקבוצה או במערך סימונים היא גם ליניארית, אך דורשת זיכרון עבור אותה רשימה. השוואת כל זוג צמתים דורשת O(m·k).
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def getIntersectionNode(next, headA, headB):
# כתבו כאן את הקודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנטים
next = [-1, 4, 1, 5, 0, 1] headA = 3 headB = 2
הפלט הצפוי
1