Middle of the Linked List
נתונה לך רשימה מקושרת חד־כיוונית המאוחסנת בשני מערכים באותו אורך. צומת i מכיל את הערך values[i] ומקושר לצומת next[i], הערך -1 מסיים את הרשימה, וראש הרשימה הוא צומת 0. הצמתים אינם מאוחסנים לפי סדר הרשימה, לכן יש לעקוב אחר הקישורים.
החזר את הערך של הצומת האמצעי. כאשר יש ברשימה מספר זוגי של צמתים, יש שני צמתים אמצעיים; החזר את הערך של השני מביניהם.
פונקציה
- valuesinteger-array
- הערך שמכילה כל צומת
- nextinteger-array
- האינדקס של הצומת שאליו כל צומת מקושר, או -1 עבור הצומת האחרון
- מחזירהinteger
- הערך של הצומת האמצעי, הצומת האמצעי השני כאשר האורך זוגי
אילוצים
1 ≤ n ≤ 5000, כאשרnהוא האורך שלvaluesושלnext.-104 ≤ values[i] ≤ 104- כל
next[i]הוא-1או אינדקס של צומת מ־0עדn-1. - החל מהצומת
0, הרשימה מבקרת בכל צומת בדיוק פעם אחת ואז מגיעה ל־-1. אין מעגל.
דוגמאות
- קלט
- values = [4, 9, 2, 7, 5]next = [3, -1, 1, 4, 2]
- פלט
- 5
- הסבר
- מעקב אחר הקישורים מהצומת
0נותן את הצמתים0, 3, 4, 2, 1, ולכן הרשימה היא4, 7, 5, 2, 9. השלישי מתוך החמישה הוא הצומת4, שערכו הוא5. האיבר האמצעי של המערך עצמו,values[2] = 2, הוא צומת אחר.
- קלט
- values = [10, 20, 30, 40, 50, 60]next = [1, 2, 3, 4, 5, -1]
- פלט
- 40
- הסבר
- כאן הצמתים מאוחסנים לפי הסדר. כשיש שישה צמתים, יש שני צמתים אמצעיים,
30ו־40, והשני הוא שנבחר.
- קלט
- values = [8]next = [-1]
- פלט
- 8
- הסבר
- האמצע של רשימה בת צומת אחד הוא הצומת עצמו.
+13 בדיקות נסתרות בשליחה
שאלת המשך
האם תוכל להחזיר את הצומת שנמצא בשליש הדרך לאורך הרשימה במעבר יחיד? באיזו מהירות ינוע כל מצביע, והיכן תעצור?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
אתה לא יודע מהו אורך הרשימה עד שמגיעים לסופה. מה אם שני הולכים היו מתחילים בראש הרשימה ואחד מהם היה נע במהירות כפולה מהשני?
כשההולך המהיר יותר מגיע לסוף, ההולך האיטי יותר עבר חצי מהמרחק, ולכן הוא נמצא בצומת האמצעי. הפרט היחיד שנותר הוא מתי לעצור כדי שבמקרה של אורך זוגי נגיע לאמצעי השני.
התחילו את
slowואתfastבצומת0. כל עודfastאינו-1וגםnext[fast]אינו-1, הזיזו את slow חוליה אחת ואת fast שתי חוליות. לאחר מכן החזירו אתvalues[slow].
פתרון
במערך, האמצע נמצא באינדקס n / 2. ברשימה מקושרת אין לך אינדקס: אפשר לדעת מה אורכה רק כשצועדים עד הסוף, וכשמגיעים לשם כבר עוברים את האמצע. אפשר להעתיק את הרשימה למערך, או לספור תחילה ואז לצעוד שוב. הפתרון האלגנטי שולח שני מצביעים לאורך הרשימה במהירויות שונות, כך שהאיטי נמצא באמצע הדרך כשהמהיר מגיע לסוף.
העתק את הערכים למערך
האינטואיציה
בבעיה הזו מצביע הוא אינדקס של צומת. מעבר לצומת הבא מתבצע באמצעות node = next[node], והגעה אל -1 פירושה שחרגתם מסוף הרשימה. בדוגמה הראשונה, המעבר מצומת 0 הוא 0 → 3 → 4 → 2 → 1 → -1.
הבעיה ברשימה היא שאי אפשר לקפוץ למיקום מסוים. לכן הופכים אותה למשהו שאפשר: עוברים על הרשימה פעם אחת ומוסיפים כל ערך למערך חדש כשמגיעים אליו. המערך הזה מכיל את הערכים לפי סדר הופעתם ברשימה — [4, 7, 5, 2, 9] בדוגמה הראשונה — והאמצע שלו נמצא באינדקס length / 2 באמצעות חלוקה שלמה.
האינדקס הזה נותן בפני עצמו את האמצעי השני כשהאורך זוגי: עבור שישה ערכים מתקבל אינדקס 3, הערך הרביעי, שהוא 40 בדוגמה השנייה. המעבר דורש זמן O(n), וההעתקה דורשת זיכרון נוסף של O(n), ששתי הגישות הבאות נמנעות ממנו.
אלגוריתם
- התחל עם מערך ריק ועם
node = 0. - כל עוד
nodeאינו-1, הוסף אתvalues[node]ועבור אלnext[node]. - החזר את האיבר באינדקס
length / 2, בעיגול כלפי מטה.
def middleNode(values, next):
in_order = []
node = 0
while node != -1:
in_order.append(values[node])
node = next[node]
return in_order[len(in_order) // 2]ספור, ואז לך עד לחצי הדרך
האינטואיציה
לא צריך את העותק כולו, אלא רק את האורך. עוברים על הרשימה פעם אחת וסופרים את הצמתים. לאחר מכן מתחילים שוב בראש הרשימה ומבצעים length / 2 צעדים, בעיגול כלפי מטה. הצומת שעוצרים בו הוא האמצעי.
למה צריך בדיוק את מספר הצעדים הזה: אחרי k צעדים נמצאים בצומת שבמיקום k, כשסופרים את הראש כמיקום 0. האמצע של רשימה באורך 5 הוא במיקום 2, והאמצע השני של רשימה באורך 6 הוא במיקום 3; בשני המקרים זהו length / 2. בדוגמה הראשונה סופרים 5, מבצעים שני צעדים 0 → 3 → 4, וקוראים את values[4] = 5.
כעת צריכת הזיכרון היא O(1). המחיר הוא מעבר שני על חצי מהרשימה, ובסך הכול 1.5n צעדים, שעדיין שייך ל-O(n).
אלגוריתם
- עבור מהצומת
0אל-1וספור את הצמתים. - חזור לצומת
0. - בצע
node = next[node]בדיוקcount / 2פעמים, בעיגול כלפי מטה. - החזר את
values[node].
def middleNode(values, next):
length = 0
node = 0
while node != -1:
length += 1
node = next[node]
node = 0
for _ in range(length // 2):
node = next[node]
return values[node]מצביעים מהירים ואיטיים
האינטואיציה
מקמו שתי מצביעים בראש הרשימה. בכל סיבוב, slow מתקדם בצומת אחד ו-fast מתקדם בשני צמתים. אחרי k סיבובים, slow נמצא במיקום k ו-fast במיקום 2k, כך ש-slow תמיד עבר חצי מהמרחק שעבר fast. כש-fast מגיע לסוף, slow נמצא באמצע, ולא היה צורך לחשב את האורך.
כלל העצירה קובע איזה אמצע תקבלו. המשיכו כל עוד fast הוא צומת ממשי ויש אחריו צומת: fast != -1 וגם next[fast] != -1. באורך אי-זוגי, fast עוצר בצומת האחרון. באורך זוגי, fast יוצא מעבר לסוף ומגיע ל--1, מה שמקדם את slow צומת אחד נוסף, אל האמצע השני. בדוגמה השנייה, slow מתקדם 0, 1, 2, 3, ואילו fast מתקדם 0, 2, 4, -1, ו-values[3] הוא 40.
בדוגמה הראשונה, slow מבקר בצמתים 0, 3, 4, ואילו fast מבקר בצמתים 0, 4, 1; צומת 1 הוא האחרון, ולכן הלולאה נעצרת כש-slow נמצא בצומת 4, והתשובה היא 5. fast מבצע בערך n צעדים ו-slow מבצע n / 2, במעבר יחיד ובשימוש בשני מספרים שלמים בזיכרון.
אלגוריתם
- הגדר את
slow = 0ואתfast = 0. - כל עוד
fast != -1וגםnext[fast] != -1, הגדר אתslow = next[slow]ואתfast = next[next[fast]]. - החזר את
values[slow].
def middleNode(values, next):
slow = fast = 0
# Stop when fast is on the last node or has stepped past it.
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
return values[slow]
מלכודות ומקרי קצה
הלולאה קצרה, ולכן הטעויות קשורות לנקודת ההתחלה שלה, לנקודת העצירה שלה ולמה שהיא מחזירה.
- החזרת
values[n / 2]. הצמתים אינם מאוחסנים לפי סדר הרשימה, ולכן האיבר האמצעי במערך הוא בדרך כלל צומת אחר. בדוגמה הראשונה מתקבל2במקום5. - קבלת האמצעי הראשון כאשר האורך זוגי. לולאה שרצה כל עוד
next[fast]וגםnext[next[fast]]מצביעים על צמתים קיימים, נעצרת סיבוב אחד מוקדם מדי ומחזירה30במקום40בדוגמה השנייה. - בדיקת
next[fast]לפניfast != -1. באורך זוגי, fast הופך ל--1, וקריאה שלnext[-1]גורמת לקריסה ברוב השפות. ב-Python, במקום זאת, היא קוראת בשקט את האיבר האחרון, וזה גרוע יותר. - הליכה של
count / 2 - 1צעדים או עיגול כלפי מעלה בגישת הספירה. ספרו את הראש כמיקום0ובצעו בדיוקcount / 2צעדים, בעיגול כלפי מטה. - החזרת אינדקס הצומת במקום הערך שלו.
- שכחת ההיסט ב-Lua וב-R, שבהן המערכים מתחילים ב-1. השאירו את אינדקסי הצמתים מבוססי 0 וקראו את
next[node + 1]. ב-Ruby וב-R המילהnextשמורה, ולכן בקוד ההתחלתי שלהן הפרמטר נקראnext_.
שאלות נפוצות4
למה מצביעים מהירים ואיטיים מוצאים את האמצע של רשימה מקושרת?
שניהם מתחילים בראש הרשימה, ובכל סיבוב המצביע המהיר מתקדם בשני צמתים, בעוד שהאיטי מתקדם בצומת אחד. אחרי k סיבובים המצביע המהיר נמצא במיקום 2k והאיטי במיקום k, בדיוק בחצי המרחק. לכן, כשהמצביע המהיר מגיע לסוף הרשימה, המצביע האיטי נמצא באמצע שלה.
מהי סיבוכיות הזמן והמרחב של מציאת האיבר האמצעי ברשימה מקושרת?
כל שלוש הגישות דורשות זמן O(n), מכיוון שאי אפשר למצוא את האמצע בלי לעבור על כמחצית מהרשימה או יותר. העתקת הערכים צורכת זיכרון נוסף של O(n). ספירה מראש והמצביעים המהיר והאיטי דורשים שניהם O(1), והמצביעים דורשים מעבר אחד בלבד.
איך מחזירים את צומת האמצע הראשון במקום את השני?
שנו את כלל העצירה כך שהמצביע המהיר יעצור סיבוב אחד מוקדם יותר: בצעו לולאה כל עוד next[fast] != -1 וגם next[next[fast]] != -1. עבור שישה צמתים, המצביע האיטי יעצור אז במיקום 2 במקום 3. בגישת הספירה, עברו (count - 1) / 2 צעדים במקום count / 2.
איפה עוד משתמשים בטכניקת המצביעים המהיר והאיטי?
אותן שתי מהירויות מזהות מחזור ברשימה מקושרת: בלולאה, המצביע המהיר מקיף את המצביע האיטי והשניים נפגשים. הן גם מוצאות היכן מתחיל מחזור ומחלקות רשימה לשניים לצורך מיון מיזוג או בדיקה אם הרשימה נקראת באותו אופן בשני הכיוונים.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def middleNode(values, next):
# כתבו כאן קודמקרה 1
מקרה 2
מקרה 3
קלט
values = [4, 9, 2, 7, 5] next = [3, -1, 1, 4, 2]
צפוי
5