假設鏈表有限、無圈、單向連結,且以順序方式獨佔修改。
溫習路線。 每次操作後追蹤節點身分和目前位置。驗證時先檢查所有要求的邊界,再重寫任何原有連結,然後使用反轉不變量。
檢查清單。 反轉重新連接兩端,也可能改變頭。無效位置需要明確處理策略。驗證過程不得解參照空指標。最壞時間 和額外參照數 假設指標操作為常數時間。
1. 兩次反轉使用目前位置
練習
(不同節點組成鏈表 。先反轉第 3 至第 6 個位置,再對所得鏈表反轉第 2 至第 4 個位置。寫出每次操作後的鏈表,並指出節點 的最終後繼。)
核心
提示(1)
先寫出第一次反轉後的鏈表,再選擇第二次操作的節點。
解答(3)
- 1
反轉第 3 至第 6 個位置
第一段為 ;反轉後得到 。
- 2
在新鏈表中讀取第二次的位置
關鍵一步
新鏈表的第 2 至第 4 個位置是 。第二次操作不再使用原鏈表中的位置。
依據: 第二次操作作用在它所收到的鏈表上。
- 3
反轉並讀出後繼
反轉 得到 。因此 的最終後繼為 。
2. 拒絕無效位置且不改變鏈表
練習
(延伸教學算法,使其在有限無圈鏈表(包括空表)上接受任意整數位置 。如果位置無效,返回 error 且不改變任何原有 next 欄位。準確描述驗證過程並給出最壞時間和輔助空間。對於 和 ,給出結果。)
核心
提示(1)
在寫入任何原有連結之前,先完成所有檢查。
解答(5)
- 1
立即拒絕不可能的整數
若 或 ,返回
error。 - 2
帶空值檢查地走到前驅
令
dummy.next=head、before=&dummy。重複 次:若before.next為空,返回error;否則令before=before.next。 - 3
帶空值檢查地走到片段之後的節點
令
after=before.next,重複 次:若after為空,返回error;否則推進after=after.next。若初始為空表,即使 也會在這裏失敗。 - 4
驗證成功後才反轉
關鍵一步
使用
first=before.next和算出的after,執行教學正文的反轉迴圈,然後賦值before.next並返回dummy.next。驗證期間不寫入原有連結,所以被拒絕的輸入保持不變;dummy 只寫臨時紀錄。依據: 驗證只讀取連結,從不寫入原有連結。
- 5
檢查例子與成本
對於 和 ,驗證到達 ,依次經過 和 ,還未完成四次推進就遇到空值,因此返回
error, 保持不變。輸入有效時,驗證和反轉合共使用 時間和 輔助參照;輸入無效時,初始檢查或某次走訪遇空值停止,因此在整數和指標操作為常數時間的模型下,界相同。輸入無圈的假設仍然必要。
快速檢查
(反轉有效鏈表的第 至第 個位置,再對同樣的第 至第 個位置反轉一次。最終的鏈表是甚麼?)
第一次反轉後,第 至第 個位置上是哪些節點?
解答 · 答案
原來的鏈表。第一次反轉只是重排第 至第 個位置內的節點,所以這些位置上仍是同一批節點;再反轉一次便還原。對 和 ,鏈表依次是 ,然後又回到 。
要避免的錯誤
反例模式
一邊驗證一邊重寫
一個誘人的設計是先反轉片段,在迴圈中途遇到空值才報告 error。對 和 ,取 prev=null 並從 開始。第 1 次迭代令 B.next=null;第 2 次令 C.next=B;第 3 次 curr 為空,程式返回 error。但鏈表已不再是 :A.next 仍是 ,而 B.next 為空, 指回 ,所以從頭無法到達 。約定要求返回 error 時鏈表不變。補救辦法是在寫入任何原有連結之前完成所有檢查。
常見錯誤
(在原鏈表中讀取第二次操作的位置)
若把第二次操作套用在原鏈表 的第 2 至第 4 個位置,會選到 。在第一次操作後的鏈表 中,這幾個節點分別位於第 2、6、5 個位置,根本不構成一個片段。第二次操作必須使用它所收到的鏈表中的位置。