Reorder List
נתונה לך רשימה מקושרת חד־כיוונית שמאוחסנת בשני מערכים באותו אורך. צומת i מכיל את הערך values[i] ומקושר לצומת next[i], -1 מסיים את הרשימה, והראש הוא צומת 0. הצמתים אינם מאוחסנים לפי סדר הרשימה, לכן יש לעקוב אחר הקישורים.
נסמן את הצמתים לפי סדר הופעתם ברשימה L0, L1, ..., Lk. סדר מחדש את הרשימה כך שתהיה L0, Lk, L1, Lk-1, L2, Lk-2, ...: הצומת הראשון, אחריו האחרון, אחריו השני, אחריו השני מהסוף, וכן הלאה. החזר את הערכים בסדר החדש.
פונקציה
- nextinteger-array
- האינדקס של הצומת שאליו כל צומת מקושר, או -1 עבור הצומת האחרון
- valuesinteger-array
- הערך שמוחזק בכל צומת
- מחזירהinteger-array
- הערכים לפי סדר הרשימה לאחר שינוי הסדר
אילוצים
1 ≤ n ≤ 4000, כאשרnהוא האורך שלnextושלvalues.-1000 ≤ values[i] ≤ 1000- כל
next[i]הוא-1או אינדקס של צומת מ־0עדn-1. - החל מהצומת
0, הרשימה מבקרת בכל צומת בדיוק פעם אחת ואז מגיעה אל-1. אין מעגל.
דוגמאות
- קלט
- next = [3, 4, -1, 1, 2]values = [1, 3, 5, 2, 4]
- פלט
- [1, 5, 2, 4, 3]
- הסבר
- בעקבות הקישורים מהצומת
0, הרשימה היא1, 2, 3, 4, 5. הראשון, האחרון, השני והאחד שלפני האחרון נותנים1, 5, 2, 4, והערך האמצעי3מגיע אחרון.
- קלט
- next = [2, 3, 1, -1]values = [10, 30, 20, 40]
- פלט
- [10, 40, 20, 30]
- הסבר
- הרשימה מבקרת בצמתים
0, 2, 1, 3וקוראת10, 20, 30, 40. הראשון והאחרון נותנים10, 40, ואז הזוג הפנימי נותן20, 30.
- קלט
- next = [-1]values = [7]
- פלט
- [7]
- הסבר
- ברשימה עם צומת אחד אין מה להזיז, ולכן התשובה היא
[7].
שאלת המשך
האם תוכל לסדר מחדש את הקישורים עצמם תוך שימוש בזיכרון נוסף של O(1)?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
כתבו את הסדר המבוקש עבור
1, 2, 3, 4, 5, 6. אילו צמתים מגיעים מהחצי הקדמי של הרשימה, ובאיזה סדר מופיעים הצמתים מהחצי האחורי?החצי האחורי מופיע בסדר הפוך:
6, 5, 4. אם החצי האחורי היה הפוך, התשובה הייתה שתי רשימות שממוזגות על ידי לקיחת צומת אחת מכל אחת בתורו.מצא את האמצע באמצעות מצביע איטי שמתקדם בקישור אחד ומצביע מהיר שמתקדם בשני קישורים. חתוך את הרשימה אחרי האמצע, הפוך את החלק השני באמצעות הפיכת הקישורים שלו, ואז שלב את שני החלקים זה בזה, צומת אחר צומת.
פתרון
הסדר החדש מתחלף בין החלק הקדמי לאחורי, אבל רשימה מקושרת חד־כיוונית מתקדמת רק קדימה. חלקו את המשימה לשלוש פעולות סטנדרטיות על רשימה: מצאו את האמצע באמצעות מצביעים איטיים ומהירים, הפכו את החצי האחורי, ושלבו את שני החצאים יחד, צומת אחד בכל פעם.
הזז את הזנב קדימה, צומת אחד בכל פעם
האינטואיציה
מצביע כאן הוא אינדקס של צומת, והתקדמות היא node = next[node]. אחרי הצומת הראשון מגיע האחרון, לכן נתק את הצומת האחרון והכנס אותו אחרי הצומת הנוכחי, ואז חזור על הפעולה שני צמתים הלאה. עבור 1, 2, 3, 4, 5 מתקבל 1, 5, 2, 3, 4, ואז 1, 5, 2, 4, 3. עצור כשנותרים פחות משני צמתים אחרי הצומת הנוכחי.
כדי למצוא את הצומת שלפני האחרון צריך לעבור עד סוף הרשימה בכל סבב. המעברים מתקצרים בשני צמתים בכל סבב, ובסך הכול נדרשות בערך n²/4 פעולות: ארבעה מיליון עבור 4000 צמתים.
אלגוריתם
- הגדר
cur = 0. - כל עוד יש לפחות שני צמתים אחרי
cur, התקדם עםbeforeמ-curעד ש-next[next[before]] == -1, כך ש-tail = next[before]הוא הצומת האחרון. - נתק אותו באמצעות
next[before] = -1, ואז הכנס אותו:next[tail] = next[cur]ו-next[cur] = tail. - העבר את
curאלnext[tail]וחזור על הפעולה. - התקדם מצומת
0ואסוף את הערכים.
def reorderList(next, values):
cur = 0
# While at least two nodes follow cur, move the last node right after cur.
while next[cur] != -1 and next[next[cur]] != -1:
before = cur
while next[next[before]] != -1: # find the node before the tail
before = next[before]
tail = next[before]
next[before] = -1
next[tail] = next[cur]
next[cur] = tail
cur = next[tail]
result = []
node = 0
while node != -1:
result.append(values[node])
node = next[node]
return resultהעתק את הערכים וקרא משני הקצוות
האינטואיציה
מערך מגיע לאיבר האחרון שלו בצעד אחד. העתק את הערכים לפי סדר הרשימה, [1, 2, 3, 4, 5] בדוגמה הראשונה, ואז קרא באמצעות lo מההתחלה ובאמצעות hi מהסוף: קח את lo, קח את hi, והזז את שניהם פנימה כל עוד lo < hi. כך מתקבלים 1, 5, 2, 4; כאשר האורך אי־זוגי, שניהם נפגשים באמצע ב־3, שמגיע אחרון.
זהו זמן O(n) וזיכרון נוסף של O(n), והקישורים לעולם אינם משתנים.
אלגוריתם
- עבור מהצומת
0והוסף כל ערך ל־inOrder. - הגדר את
lo = 0ואתhiכאינדקס האחרון. - כל עוד
lo < hi, הוסף אתinOrder[lo]ואתinOrder[hi], ואז קדם אתloוהקטן אתhi. - אם
lo == hi, הוסף את הערך האמצעי.
def reorderList(next, values):
# Write the values out in list order.
in_order = []
node = 0
while node != -1:
in_order.append(values[node])
node = next[node]
# Take from the front and the back in turn.
result = []
lo, hi = 0, len(in_order) - 1
while lo < hi:
result.append(in_order[lo])
result.append(in_order[hi])
lo += 1
hi -= 1
if lo == hi: # odd length: the middle value comes last
result.append(in_order[lo])
return resultמצא את האמצע, הפוך את החצי האחורי, שזור
האינטואיציה
עבור 1, 2, 3, 4, 5, 6 התשובה היא 1, 6, 2, 5, 3, 4: החצי הקדמי 1, 2, 3 לפי הסדר, לסירוגין עם החצי האחורי 4, 5, 6 כשהוא נקרא לאחור. לכן חותכים את הרשימה באמצע, הופכים את החצי האחורי ושוזרים.
slow מתקדם בקישור אחד, ואילו fast מתקדם בשני קישורים, ולכן slow נעצר בצומת האחרון של החצי הקדמי: בצומת 3, גם כשיש חמישה צמתים וגם כשיש שישה. חיתוך אחריו נותן לחצי הקדמי צומת אחד נוסף כשהאורך אי-זוגי, וצומת זה מסיים את התשובה. בשזירה לוקחים צומת אחד מכל חצי לסירוגין, עד שנגמר החצי האחורי.
ניגשים לכל צומת מספר קבוע של פעמים, תוך שימוש בכמה אינדקסים בזיכרון. R מעתיקה את וקטור הקישורים בשינוי הראשון שלו, ולכן ב-R הזיכרון הוא O(n).
אלגוריתם
- התקדם עם
slowחוליה אחת ועםfastשתי חוליות, כל עודnext[fast]ו-next[next[fast]]אינם-1. - הגדר
second = next[slow], ואזnext[slow] = -1. - הפוך את הרשימה שמתחילה ב-
second; הראש החדש שלה הואprev. - שזור: כל עוד
secondאינו-1, קשר אתfirstאלsecondואתsecondאל הערך הישן שלnext[first], ואז התקדם עם שניהם. - עבור מהצומת
0ואסוף את הערכים.
def reorderList(next, values):
# 1. Find the middle: slow stops on the last node of the first half.
slow = fast = 0
while next[fast] != -1 and next[next[fast]] != -1:
slow = next[slow]
fast = next[next[fast]]
second = next[slow]
next[slow] = -1 # cut the list in two
# 2. Reverse the second half.
prev = -1
while second != -1:
after = next[second]
next[second] = prev
prev = second
second = after
# 3. Weave: one node from the front half, one from the reversed back half.
first, second = 0, prev
while second != -1:
first_after, second_after = next[first], next[second]
next[first] = second
next[second] = first_after
first, second = first_after, second_after
result = []
node = 0
while node != -1:
result.append(values[node])
node = next[node]
return result
מלכודות ומקרי קצה
- לא לנתק את הרשימה אחרי האמצע. בלי
next[slow] = -1, החצי הקדמי עדיין מצביע אל החצי האחורי, ואחרי השזירה הרשימה מסתובבת בחזרה אל עצמה. - דריסת קישור לפני ששומרים אותו. בהיפוך ובשזירה, יש לקרוא את
next[node]לתוך משתנה תחילה, אחרת שאר הרשימה הולכת לאיבוד. - להמשיך לשזור עד שהחצי הקדמי מסתיים. באורך אי־זוגי, הלולאה הזאת רצה פעם נוספת כש-
secondהוא-1וקוראת אתnext[-1]. - לקרוא את סדר המערך כאילו הוא סדר הרשימה. בדוגמה הראשונה,
valuesהוא[1, 3, 5, 2, 4], אבל הרשימה נקראת1, 2, 3, 4, 5. - ב-Lua וב-R מערכים מתחילים ב-1. יש להשאיר את האינדקסים של הצמתים מבוססי-0 ולקרוא את
next[node + 1].
שאלות נפוצות3
למה להפוך את החצי השני של הרשימה?
התשובה קוראת את החצי האחורי מהצומת האחרון שלו לראשון, ורשימה מקושרת חד־כיוונית מתקדמת רק קדימה. היפוך של החצי האחורי פעם אחת, ב־O(n), מאפשר למיזוג לעבור על שני החצאים קדימה.
מהי סיבוכיות הזמן של Reorder List?
השיטה במקום פועלת בזמן O(n) ודורשת O(1) זיכרון נוסף: מציאת האמצע, היפוך ושזירה מבקרים כל אחד בכל צומת מספר קבוע של פעמים. העתקת הערכים למערך אורכת גם היא זמן O(n), אך דורשת זיכרון O(n), והזזת הזנב קדימה צומת אחד בכל פעם אורכת O(n²).
איפה נמצא האמצע כאשר לרשימה יש מספר זוגי של צמתים?
עצור את המצביע האיטי בצומת האחרון של החצי הקדמי. כשיש שישה צמתים, בכל חצי יש שלושה; כשיש חמישה, יש שלושה בשלב הקדמי ושניים באחורי. הצומת הנוסף מסיים את התשובה, ושם הסדר מציב את הערך האמצעי.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def reorderList(next, values):
# כתבו כאן את הקודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנטים
next = [3, 4, -1, 1, 2] values = [1, 3, 5, 2, 4]
הפלט הצפוי
[1, 5, 2, 4, 3]