鏈表有限、無圈、單向連結;位置從 1 開始且有效。使用教學正文的算法和 dummy 節點約定。
溫習路線。 重寫連結前確定 before、first 和 after。追蹤保存的下一節點參照及反轉前綴,只在迴圈結束後重新連接前驅。
檢查清單。 修改 curr.next 前先保存它。把 prev 初始化為 after。若 ,返回 dummy 更新後的 next;若 ,after 為空。必須保留原節點和後綴。
1. 追蹤中間片段
練習
(對於 ,反轉第 3 至第 5 個位置。給出 before、after 及每次迴圈迭代後的 prev 和 curr,並寫出返回的鏈。)
核心
提示(1)
先找出
before和after,並把prev起初設為after。
解答(3)
- 1
找出邊界節點
before=B,after=F。初始prev=F、curr=C。 - 2
執行三次迭代
關鍵一步
第一次迭代後
prev=C、curr=D,鏈為 ;第二次後prev=D、curr=E,鏈為 ;第三次後prev=E、curr=F,鏈為 。依據: 每次迭代都在改寫
curr.next之前先保存它。 - 3
重新連接前驅
由於
curr == after,停止並令 。返回鏈為 。
2. 頭指標發生變化
練習
(鏈表含不同節點,值為 。反轉第 1 至第 3 個位置。指出 dummy 最終的 next、舊頭最終的後繼和返回鏈表。如果調用者從未收到返回的頭,為甚麼僅對區域變量 head 賦值不夠?)
核心
提示(1)
時,哪個節點擔當
before的角色?
解答(3)
- 1
找出邊界節點
before是 dummy,after是值為 4 的節點。反轉片段 得到 。 - 2
讀出最終連結
dummy 最終的
next是節點 9;舊頭 7 現在指向 4。返回 dummy 的next。 - 3
解釋為何需要返回的頭
若函數只改變其區域
head變量,這個賦值本身不會改變調用者獨立的頭變量;調用者必須使用返回的頭,或明確傳入對其頭變量的可修改參照。節點連結已經改變,所以保留舊頭只會看到從 7 開始的後綴。
快速檢查
(對 ,、,before、after 及返回的鏈各是甚麼?)
片段延伸到鏈表末端時,after 是甚麼?
解答 · 答案
before 是 dummy,after 為空,因為片段結束於最後一個節點。以 prev=null 開始,迴圈得到 ,dummy 的 next 是 。反轉整個鏈表是 、 的特例。
要避免的錯誤
常見錯誤
(在迴圈之前就重新連接前驅)
若在迴圈之前執行 before.next = prev,此時 prev 仍等於 after。在「追蹤中間片段」一題中,這會令 ,得到 ,節點 、、 從頭已無法到達。前驅必須在迴圈建好反轉鏈之後才重新連接。