反轉整個鏈表會改變頭指標。只反轉中間片段還有兩個任務:把前驅重新連到片段的新頭,並把原頭連到不變的後綴。寫程式前先畫指標圖,可以看清這兩個任務。
本章延伸課程的指標、記憶體與結構體和作為遞歸 ADT 的鏈表材料。原地指標算法是推導應用,不表示函數式 ADT 必然使用修改操作。
約定與算法
定義 2.3.1
(片段反轉的約定)
輸入為有限、無圈的單向鏈表,含 個不同節點。每個節點有 next 參照和一個值。位置從 1 開始,滿足 。反轉第 到第 個位置上的節點;保留片段以外的節點、值和順序。返回可能改變的頭指標。操作期間不分配或釋放節點;臨時 dummy 紀錄除外,它不是返回鏈表中的節點。假設有獨佔權限修改片段節點的 next 欄位,以及在 時修改前驅的 next 欄位;外部節點別名仍指向原節點,但可能觀察到這些欄位的變化。
reverseSegment(head, l, r): # 前提:1 <= l <= r <= n
dummy.next = head
before = 指向 dummy 的參照
重複 l-1 次:
before = before.next
first = before.next
after = first
重複 r-l+1 次:
after = after.next
prev = after
curr = first
當 curr != after:
next = curr.next
curr.next = prev
prev = curr
curr = next
before.next = prev
返回 dummy.next
dummy 是帶 next 欄位的臨時紀錄。當 時,before 指向 dummy,因此同一最終賦值可更新返回的頭。當 時,after 為空;令 prev = after,使反轉後原片段頭以空參照結尾。指標 after 在改變連結之前找到。重寫 curr.next 前先保存變量 next,因此未處理部分仍可存取。
為甚麼恰好反轉所需節點
定理 2.3.2
(片段反轉的正確性)
設鏈表由互不相同的節點 組成,且 。則 reverseSegment(head, l, r) 返回鏈表 的頭,不分配也不釋放任何鏈表節點。它作 次指標步驟,並使用 個輔助參照。
證明
(片段已反轉前綴的不變量)
把原片段寫成 ,其中 、,之後是不變的後綴,從 after 開始。經過 次迭代,:當 時,prev 指向鏈 的頭;當 時,它等於 after。若 ,curr 指向 ,未處理的連結仍經過 到達 after;若 ,則 curr == after。
起初 ,不變量成立。一次迭代保存下一個未處理節點,使 指向已反轉前綴,再推進兩個參照。這樣已反轉前綴恰好多一個節點,同時保留剩餘鏈。 時迴圈停止,prev 指向 。賦值 before.next = prev 把不變的前綴連接到該鏈。因此每個原節點在返回鏈表中恰好保留一次,後綴也得以保留。節點 從不被寫入,只有 before.next 被賦值一次;從 after 起的後綴只被讀取,所以返回的鏈表恰好就是定理所述的鏈表。
迴圈期間,從舊頭能到達的鏈表未必已是最終鏈表;curr 和 prev 是必需的工作參照。並發讀者觀察中間連結不屬於這一順序執行約定。
證明透視
未處理節點靠甚麼保持可達?
第一次重寫後,沿原片段頭前進會到達保存的後綴,而不是餘下片段。局部參照 curr 保留了下一個未處理節點。同時 prev 的鏈以 after 結尾,因此迴圈結束時原片段頭已連回不變的後綴;最後一次賦值只負責重新連接前驅。
例題
例題 2.3.3
(反轉五個節點的中間片段)
不同節點 中,令 。前驅為 ,first 是 ,after 是 。起初 prev=E、curr=B。三次迭代依次建立 B -> E、C -> B -> E、D -> C -> B -> E;此時 curr 已到 。最後令 A.next=D,返回鏈為 。後綴從同一個節點 開始,而非從它的值的副本開始。
例題 2.3.4
(從頭部開始的片段)
對互不相同的節點 ,令 、。此時 before 是 dummy,first 是 ,after 是 。起初 prev=C、curr=A。第 1 次迭代:next=B,A.next=C,prev=A,curr=B。第 2 次迭代:next=C,B.next=A,prev=B,curr=C,等於 after,迴圈停止。令 dummy.next=B 並返回,得到 。調用者原來的 head 即 現在是第二個節點,所以調用者必須使用返回的頭。
例題 2.3.5
(邊界情況:到尾部結束的片段與單一節點的片段)
取 ,、。此時 before 是 ,first 是 。找 after 要從 走三步:、,然後是空。所以 prev 起初為空。迴圈依次令 、、,結束時 curr 為空,等於 after。然後 A.next=D 得到 :片段原來的頭 現在成為鏈表的結尾。
再取 ,。此時 first=B、after=C、prev=C。唯一一次迭代令 B.next=C、prev=B、curr=C。賦值 A.next=B 沒有任何改變:反轉單一節點的片段,結果就是它自己。
要避免的錯誤
常見錯誤
(像反轉整個鏈表那樣把 prev 設為空)
像反轉整個鏈表那樣使用 prev = null,會切斷後綴。對 ,、,第一次迭代令 B.next=null,最終鏈表是 ,節點 丟失了。把 prev 起初設為 after,才能把片段原來的頭重新連到後綴。
常見錯誤
(忘記最後的重新連接)
若沒有 before.next = prev,前驅仍指向片段原來的頭。對 ,、,反轉後的鏈 存在,但 A.next 仍是 ,而 現在是 。結果是 ;節點 和 無法從頭到達。
反例模式
超出末端的位置並非無害
一個誘人的說法是:既然尋找 after 只是走到空為止, 的位置只會反轉到末端。取 ,、。此時 first 是 ,尋找 after 要走 步:第一步到 ,第二步到空,第三步要讀取 null.next。這段走訪在任何連結被改變之前就已失敗。
是約定的一部分。要檢查它,必須先數節點個數,這是額外的工作,也是另一份約定。
成本與限制
定位 before 和 after 需要 次指標步驟;反轉需要 次迭代,所以總時間為 ,最壞為 。算法使用 個輔助參照,不計已有鏈表。這些界假設指標操作為常數時間且位置有效;檢查任意無效位置或偵測輸入圈需要另行約定,並可能需要額外工作。值不必互不相同,因為片段由位置和節點身分決定,而非值是否相等。
習題與解答
快速檢查
(對 及 ,算法返回甚麼?)
first 是哪個節點?after 又是哪個?
解答 · 答案
鏈表不變,仍是 。此時 first 是 ,after 是 。唯一一次迭代令 C.next=D,所以 prev 是 ,而 B.next=C 恢復原有的連結。反轉單一節點的片段,結果就是它自己。
快速檢查
(對 、、,定位 before 和 after 共需幾次指標步驟?迴圈迭代幾次?)
分開計算兩次搜尋的步數。
解答 · 答案
定位 before 需要 步,由 dummy 走到 。定位 after 需要 步,由 走到 。合共 步。迴圈執行 次。
快速檢查
(為何函數返回 dummy.next 而不是 head?)
時,原來的頭會怎樣?
解答 · 答案
時,原來的頭是被反轉片段的第一個節點,反轉後它不再是第一個。最後的賦值把新的第一個節點存入 dummy.next。在 、、 的例子中,head 是 ,但正確的結果是 。