Reverse Linked List
נתונה לך רשימה מקושרת חד־כיוונית המאוחסנת במערך next: צומת i מקושר לצומת next[i], -1 מסיים את הרשימה, והראש הוא צומת 0. הצמתים אינם מאוחסנים לפי סדר הרשימה, לכן יש לעקוב אחר הקישורים.
הפוך את הרשימה על ידי הפיכת הכיוון של כל קישור, כך שהצומת שהיה אחרון יהפוך לראש והצומת 0 יהפוך לצומת האחרון, המקושר אל -1. החזר את מערך next המעודכן, שאורכו זהה לאורך מערך הקלט.
פונקציה
- nextinteger-array
- האינדקס של הצומת שאליו כל צומת מקושר, או -1 עבור הצומת האחרון
- מחזירהinteger-array
- המערך הבא של הרשימה ההפוכה
אילוצים
1 ≤ next.length ≤ 5000- כל
next[i]הוא-1או אינדקס של צומת מ-0עדnext.length-1. - החל מהצומת
0, הרשימה מבקרת בכל צומת בדיוק פעם אחת ואז מגיעה אל-1. אין מעגל.
דוגמאות
- קלט
- next = [1, 2, 3, -1]
- פלט
- [-1, 0, 1, 2]
- הסבר
- הרשימה היא
0 → 1 → 2 → 3. לאחר היפוכה היא3 → 2 → 1 → 0, לכן הצומת3מקושר ל־2, הצומת2ל־1, הצומת1ל־0, והצומת0ל־-1.
- קלט
- next = [2, -1, 3, 1]
- פלט
- [-1, 3, 0, 2]
- הסבר
- הרשימה היא
0 → 2 → 3 → 1, ובהיפוך היא1 → 3 → 2 → 0. כתיבת כל קישור חדש באינדקס של הצומת שלו נותנת[-1, 3, 0, 2]. היפוך המערך עצמו היה נותן[1, 3, -1, 2], וזה לא אותו הדבר.
- קלט
- next = [-1]
- פלט
- [-1]
- הסבר
- צומת אחד הוא ההופכי של עצמו. הוא נשאר הראש והזנב, ועדיין מקושר ל־
-1.
+11 בדיקות נסתרות בשליחה
שאלת המשך
האם תוכל להפוך רק את החלק ברשימה שבין המיקום left למיקום right, ולהשאיר את הצמתים שלפניו ואחריו במקומם?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
כל קישור
a → bצריך להפוך ל־b → a. כשאתה עומד על צומת, מה עליך לדעת כדי להפוך את כיוון הקישור שלו?צריך את הצומת שממנו הגעת, לכן יש לעבור ברשימה ולשמור את הצומת הקודם. אבל ברגע שדורסים את
next[node], הדרך קדימה נעלמת. יש לשמור אותה לפני שמשנים משהו.התחילו עם
prev = -1ועםnode = 0. כל עודnodeאינו-1: זכרו אתnext[node], הגדירו אתnext[node]ל-prev, ואז העבירו אתprevאלnodeואתnodeאל הערך השמור. החזירו אתnext.
פתרון
היפוך של רשימה אינו מזיז אף צומת; הוא הופך את הכיוון של כל קישור. הבעיה היא שהקישור של צומת הוא הדרך היחידה להגיע לשאר הרשימה, ולכן ברגע שדורסים אותו, כל מה שאחריו אובד. אפשר למנוע את הבעיה על ידי רישום הסדר מראש, או לעבור על הרשימה פעם אחת בעזרת שלושה מצביעים ששומרים את הדרך קדימה לפני הפיכת כל קישור.
רשום את הסדר, ואז קשר מחדש
האינטואיציה
בבעיה הזו, מצביע הוא אינדקס של צומת, והמעבר קדימה הוא node = next[node]. עבור מהצומת 0 עד שתגיע ל־-1, ורשום כל צומת שאתה עובר בו. בדוגמה השנייה מתקבל הסדר [0, 2, 3, 1].
ברשימה ההפוכה, כל צומת מקושר לצומת שקדם לו בסדר הזה: 1 מקושר ל־3, 3 ל־2, 2 ל־0. לצומת הראשון בסדר, הראש הישן, אין צומת שקדם לו, ולכן הוא מקושר ל־-1. מלא מערך חדש בקישורים האלה והחזר אותו.
מכיוון שכל קישור נכתב במערך חדש, שום דבר לא נדרס בזמן שאתה עדיין זקוק לו, ולכן קשה לטעות בגרסה הזו. זמן הריצה הוא O(n), ונדרשים O(n) זיכרון נוסף עבור הסדר והמערך החדש.
אלגוריתם
- עברו מהצומת
0אל-1והוסיפו כל צומת ל־order. - צרו מערך חדש באותו אורך.
- הגדירו את הערך של
order[0]ל־-1. - עבור כל
k ≥ 1, הגדירו את הערך שלorder[k]ל־order[k-1]. - החזירו את המערך החדש.
def reverseList(next):
order = []
node = 0
while node != -1:
order.append(node)
node = next[node]
reversed_next = [0] * len(next)
reversed_next[order[0]] = -1 # the old head ends the new list
for k in range(1, len(order)):
reversed_next[order[k]] = order[k - 1]
return reversed_nextהפכו את הקישורים בפעולה אחת
האינטואיציה
אפשר להפוך כל קישור ברגע שמגיעים לצומת שלו, אם זוכרים מאיזה צומת הגעתם. שמרו את prev, הצומת שמאחוריכם, כשהערך ההתחלתי הוא -1, כי הראש הישן יהפוך לצומת האחרון. בצומת node, הקישור next[node] מצביע קדימה; הציבו בו את prev כדי שיצביע לאחור.
הכתיבה הזו הורסת את הדרך היחידה שלכם להמשיך קדימה, לכן שמרו אותה תחילה במשתנה שלישי, after = next[node]. לאחר מכן הפכו את הקישור והזיזו את שני המצביעים צעד אחד: prev = node, node = after. בכל רגע, הצמתים שמאחוריכם יוצרים רשימה הפוכה שראשה הוא prev, והצמתים שלפניכם הם שאר הרשימה שטרם שונתה, החל מ-node. כש-node מגיע ל--1, כל הקישורים כבר הפוכים ו-prev הוא הראש החדש.
בדוגמה השנייה, המצביעים עוברים דרך הצמתים 0, 2, 3, 1, וכותבים next[0] = -1, next[2] = 0, next[3] = 2 ו-next[1] = 3. מבקרים בכל צומת פעם אחת, בזמן O(n), והזיכרון היחיד שנדרש הוא שלושה מספרים שלמים, O(1).
אלגוריתם
- הגדר את
prev = -1ואתnode = 0. - כל עוד
nodeאינו-1, שמור אתafter = next[node]. - הגדר את
next[node] = prev. - המשך הלאה:
prev = node, ואזnode = after. - החזר את
next.
def reverseList(next):
prev = -1 # the node behind the current one; the old head will point to -1
node = 0
while node != -1:
after = next[node] # save the rest of the list before cutting the link
next[node] = prev
prev = node
node = after
return next
מלכודות ומקרי קצה
כמעט כל באג כאן קשור לסדר של שלוש ההשמות, או לשני הקצוות של הרשימה.
- דריסת
next[node]לפני ששומרים אותו. אחריnext[node] = prevהקישור הישן קדימה אובד, והמעבר קופץ לאחור במקום להמשיך לצומת הבא. - אתחול
prevלערך שאינו-1. הראש הישן חייב לסיים את הרשימה החדשה. אתחול ל־0גורם לצומת0לקשר את עצמו לעצמו. - היפוך המערך במקום הקישורים. הצמתים אינם מאוחסנים לפי סדר הרשימה, והתשובה משאירה כל צומת באינדקס שלו; רק הערכים משתנים. היפוך
[2, -1, 3, 1]נותן[1, 3, -1, 2], ולא[-1, 3, 0, 2]. - עצירה צומת אחד מוקדם מדי באמצעות לולאה עם
next[node] != -1. צריך להפוך גם את הקישור של הצומת האחרון, לכן יש להמשיך בלולאה כל עודnode != -1. - היפוך באמצעות רקורסיה ברשימה ארוכה. רשימה של 5000 צמתים דורשת 5000 קריאות מקוננות, מעבר למגבלה של Python, שהיא 1000.
- שכחת ההיסט ב־Lua וב־R, שבהן המערכים מתחילים ב־1. יש להשאיר את אינדקסי הצמתים מבוססי־0 ולקרוא את
next[node + 1]. Ruby ו־R שומרות את המילהnext, ולכן בדוגמאות שלהן הפרמטר נקראnext_.
שאלות נפוצות4
איך הופכים רשימה מקושרת במקום?
עבור על הרשימה בעזרת שני מצביעים: prev שמתחיל ללא ערך ו-node שמתחיל בראש הרשימה. בכל צומת, שמור את הצומת הבא שלו, הפנה את הקישור שלו אל prev, ואז הזז את prev ואת node צעד אחד קדימה. כשנגמרים הצמתים של node, prev הוא ראש הרשימה ההפוכה.
מהי סיבוכיות הזמן והמרחב של היפוך רשימה מקושרת?
הגרסה האיטרטיבית מבקרת בכל צומת פעם אחת, בזמן O(n), ושומרת שלושה מצביעים, עם O(1) מקום נוסף. העתקת הסדר למערך תחילה דורשת גם היא זמן O(n), אך זקוקה ל-O(n) מקום נוסף. גרסה רקורסיבית משתמשת ב-O(n) מקום עבור מחסנית הקריאות.
האם אפשר להפוך רשימה מקושרת באופן רקורסיבי?
כן. הפוך את כל מה שאחרי הראש, ואז תן לצומת הבא הישן של הראש להצביע בחזרה אל הראש והגדר את הקישור של הראש לריק. זה נקרא היטב, אבל הוא מבצע קריאה מקוננת אחת לכל צומת, ולכן רשימה ארוכה עלולה לגרום לחריגה ממחסנית הקריאות. Python עוצר כברירת מחדל אחרי 1000 קריאות, ורשימה של 5000 צמתים חורגת ממספר זה.
למה היפוך של רשימה מקושרת דורש שלושה מצביעים?
כדי להפוך את הקישור של צומת, צריך את הצומת עצמו ואת הצומת שלפניו, כלומר שני מצביעים. המצביע השלישי מחזיק את הצומת שאחריו, כי הפיכת הקישור מוחקת את ההפניה היחידה לשאר הרשימה. בלעדיו, אי אפשר להמשיך לעבור על הרשימה.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def reverseList(next):
# כתבו כאן את הקודמקרה 1
מקרה 2
מקרה 3
קלט
next = [1, 2, 3, -1]
צפוי
[-1, 0, 1, 2]