單向鏈表的節點只向前連結;反轉時既要改變連結,也要保留尚未處理節點的入口。本節推導迭代算法及其不變量。
1. 前置條件與程式
定義 2.2.1
(原地反轉鏈表的前置條件)
假設 head 是 NULL,或指向一條有限、無環鏈中第一個有效且仍存在的 Node。每個 next 指向鏈中的下一節點或 NULL。調用者允許函數修改所有連結,並確保沒有與修改衝突的並行存取。節點值可重複。函數不配置、複製或釋放節點;返回新的頭指標。已有別名仍指向同一批活節點,但看到的連結會改變;調用者必須以返回指標作新的頭。
#include <stddef.h>
typedef struct Node {
int value;
struct Node *next;
} Node;
Node *reverse_list(Node *head) {
Node *prev = NULL;
Node *cur = head;
while (cur != NULL) {
Node *next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
必須在改寫 cur->next 之前保存 next:改寫後該欄位向後指,不再通往未處理的後綴。程式沒有釋放 cur 或 prev。若忽略返回值,調用者的舊頭可能已變為尾節點,無法從它到達反轉後的其餘節點。
2. 迴圈不變量
把原來的節點依序記作 。處理了 個節點後,每次迭代開始時,,而:
prev依次指向 所成的鏈; 時為NULL。cur依原次序指向 所成的鏈; 時為NULL。- 兩鏈互不相交,合起來恰好包含所有原節點各一次,且各以
NULL結束。
定理 2.2.2
(鏈表反轉的正確性與成本)
設 head 滿足前置條件,原節點為 ()。則 reverse_list(head) 返回一條以 NULL 結尾的鏈的第一個節點,該鏈恰按此次序包含 ;若 則返回 NULL。迴圈體恰好執行 次,函數使用 輔助空間,並且不配置也不釋放任何節點。
證明
(初始、保持與終止)
初始。 時,prev 是 NULL,cur 是原鏈的頭。保持。 若 cur 非空,先保存其下一指標,便仍能到達剩餘後綴;把其連結改指 prev,就把原序列的下一節點加到反轉前綴之首。更新兩個局部指標後,不變量對 成立,兩鏈仍互不相交且以空指標結束。終止。 每次迭代使未處理後綴長度減一。因 有限,cur 最終成為 NULL;此時 ,prev 是全部原節點反序所得鏈的頭,共經過恰好 次迭代。
證明透視
為何不變量必須描述兩條鏈
這個不變量同時談到兩條鏈,其中第三項承擔了關鍵:prev 與 cur 把所有節點劃分開。正是這個劃分令單一的寫入 cur->next = prev 安全。它只改變恰好一個節點 cur 的連結,該節點剛離開未處理的鏈,而該連結的舊值已先保存在 next 中。除 cur 外,兩條鏈上的節點都沒有被觸動。
每個假設只在一處使用。有限性給出終止。無環且以空指標結束,用於初始情形:cur 必須是一條以 NULL 結束的鏈的頭。節點身分互異(而非數值互異)給出互不相交的條款。證明在 時完結:未處理的鏈為空,所以 prev 反序持有所有節點。若沒有無環這個條件,初始情形便不成立,下一個例子說明這一點。
空鏈返回 NULL;單節點鏈返回同一節點,其連結仍為 NULL。算法走訪 個節點,時間為 ,把空鏈固定成本一併計算可寫成 ;輔助空間為 。成本分析採用這種表示法及指標操作單位成本模型,不直接推論其他表示法。
反例模式
有環的鏈不是一條長鏈
一個誘人的說法是:迴圈只是向前走到遇見 NULL 為止,所以對碰巧有環的鏈也能反轉。取節點 與 ,有 a->next = b 及 b->next = a,這違反前置條件。第 1 次迭代:cur = a,next = b,設 a->next = NULL,於是 prev = a、cur = b。第 2 次迭代:next = b->next = a,設 b->next = a,於是 prev = b、cur = a。第 3 次迭代:next = a->next = NULL,設 a->next = b,於是 prev = a、cur = NULL。調用返回 ,但此時 a->next = b 且 b->next = a:返回的鏈永遠到不了 NULL。
迴圈之所以停止,只是因為第一次迭代碰巧把 a->next 改成了 NULL。後置條件(以空指標結束的反轉鏈)不成立。補救辦法就是前置條件本身:證明依賴有限且以空指標結束的鏈;對無效輸入不作聲稱。
3. 指標追蹤
例題 2.2.3
(追蹤四個節點)
對 12 -> 4 -> 15 -> 6 -> NULL,下表列出每次迭代開始時的兩條鏈,最後一行為終止狀態。這裏用數值標記節點;證明使用節點身分,數值重複時也成立。
| 已處理 | prev 鏈 | cur 鏈 |
|---|---|---|
| 0 | NULL | 12 -> 4 -> 15 -> 6 -> NULL |
| 1 | 12 -> NULL | 4 -> 15 -> 6 -> NULL |
| 2 | 4 -> 12 -> NULL | 15 -> 6 -> NULL |
| 3 | 15 -> 4 -> 12 -> NULL | 6 -> NULL |
| 4 | 6 -> 15 -> 4 -> 12 -> NULL | NULL |
當 cur 成為 NULL,函數返回 prev。原本指向節點 12 的指標仍指向同一節點,但它現在是尾節點,不能代表整條反轉後的鏈。
概念視角結構
把反轉看成兩個堆疊之間的搬移
把 prev 所指的鏈看作頭在頂端的堆疊,把 cur 所指的鏈看作第二個堆疊,頭同樣在頂端。每次迭代從 cur 堆疊彈出頂端節點,再推入 prev 堆疊;被寫入的指標只有新頂端指向舊頂端的連結。把所有節點從一個堆疊搬到另一個堆疊,次序便被反轉,這正是不變量的另一種說法:搬了 次後,prev 堆疊由頂至底為 至 。把節點搬回去就恢復原來的次序,所以連續反轉兩次會得回原來的鏈表。
例題 2.2.4
(數值重複,節點相異)
設鏈為 p -> q -> r -> NULL,其中 p 與 q 的值都是 8,r 的值是 3。第 1 次迭代:next = q,p->next = NULL,prev = p,cur = q。第 2 次迭代:next = r,q->next = p,prev = q,cur = r。第 3 次迭代:next = NULL,r->next = q,prev = r,cur = NULL。調用返回 r -> q -> p -> NULL,即依次為原來第三、第二、第一個節點。兩個值為 8 的節點仍是兩個節點,次序顛倒;相同數值不會令節點合併。
例題 2.2.5
(邊界情況:空鏈與單一節點)
對空鏈,cur = head = NULL,迴圈體一次也不執行,函數返回 prev,即 NULL。對單一節點 p,迴圈體執行一次:next = NULL,p->next = prev = NULL,prev = p,cur = NULL。函數返回 p,其連結仍為 NULL;反轉單節點鏈沒有任何改變。這就是定理中 與 的情形。
4. 檢查與練習
常見錯誤
(先改寫連結才保存它)
若迴圈先執行 cur->next = prev,再讀取 next = cur->next,則 next 會等於 prev。對 1 -> 2 -> 3,第一次迭代就令 cur 成為 NULL,函數只返回節點 1,節點 2 和 3 無法從結果到達。其他獨立別名可能碰巧保留它們的入口,但算法不能依賴這一點。
常見錯誤
(丟棄返回的頭指標)
對 1 -> 2 -> 3 調用 reverse_list(head) 之後,調用者的變量 head 仍指向節點 1,但它現在是尾節點,其 next 為 NULL。從 head 出發只看到一個節點的鏈。新的頭是返回的指標,即節點 3。
快速檢查
(把有效鏈反轉兩次,解釋為何返回鏈恢復原有次序及節點身分。)
對第一次調用的輸出應用定理。
解答 · 答案
由定理,第一次調用返回有效的鏈 ,它同樣滿足前置條件。第二次調用把它反轉成 。每次調用都只重新連結現有節點,不配置也不釋放節點,所以同樣的節點以原有次序出現。
快速檢查
(若把迴圈條件由 cur != NULL 改為 cur->next != NULL,對 1 -> 2 -> 3 函數返回甚麼?)
追蹤到 cur->next 為 NULL 為止。
解答 · 答案
第 1 次迭代(cur 是節點 1):next 是節點 2,1->next = NULL,prev 是節點 1,cur 是節點 2。第 2 次迭代(cur 是節點 2,且 cur->next 是節點 3):next 是節點 3,2->next = 1,prev 是節點 2,cur 是節點 3。此時 cur->next 為 NULL,迴圈停止,函數返回節點 2,即鏈 2 -> 1 -> NULL。節點 3 從未被處理,也不在結果之中。
快速檢查
(在 12 -> 4 -> 15 -> 6 的追蹤中,處理了兩個節點之後,prev 與 cur 各指向哪條鏈?)
用 的不變量。
解答 · 答案
prev 指向 ,即 4 -> 12 -> NULL;cur 指向 ,即 15 -> 6 -> NULL,與已處理 2 個節點那一行相同。