合併兩個已排序的鏈表是一個小型算法,卻要履行好幾項責任:它必須把數值排好次序、每個節點恰好保留一次,並且令結果以 null 結尾。
1. 穩定的破壞性合併
定義 18.1.1
(穩定的破壞性合併)
假設有兩個互不相交、有限、無環的單向鏈表,按鍵值非遞減次序排列。每個節點包含一個鍵值及 next。合併過程可以重新連結輸入節點:之後調用者不得再把原來的鏈表頭當作獨立鏈表使用。相等的鍵值可以屬於不同節點。為使合併穩定,當兩邊最前的鍵值相等時,先選取左鏈表的節點;除此以外,不要改變任何一個輸入鏈表內部的次序。
merge(left, right):
dummy.next = null
tail = dummy
while left != null and right != null:
if left.key <= right.key:
chosen = left; left = left.next
else:
chosen = right; right = right.next
tail.next = chosen
tail = chosen
if left != null: tail.next = left
else: tail.next = right
return dummy.next
dummy 是一個臨時的哨兵,並非輸出的數據節點。要在之後的迭代覆寫任何連結之前,先推進相關的輸入指標,以保存後繼節點。在下一次賦值之前,舊的 tail.next 仍可能指向某個輸入後綴,因此在迴圈期間只讀取輸出直至 tail 為止;它還不是一個獨立、以 null 結尾的鏈表。
定理 18.1.2
(破壞性合併的正確性與成本)
設 left 與 right 是互不相交、有限、無環的單向鏈表,分別有 與 個節點,且都按鍵值非遞減次序排列。則 merge(left, right) 傳回一個以 null 結尾的鏈表,其中兩個輸入的每個節點恰好出現一次,並按鍵值非遞減次序排列。每個輸入的節點保持輸入時的次序,而且每個左節點都排在鍵值相等的右節點之前。當 時,合併至多作 次鍵值比較,否則不作比較;它需時 ,並使用 的輔助指標空間(不計輸入節點)。
證明
(關於輸出前綴與兩個後綴的不變量)
把至今已移動的節點稱為已選取節點。每次檢驗迴圈條件時,下列各項成立。(i) 從 dummy 沿 next 走到 tail,恰好依選取次序訪問所有已選取節點。(ii) 這段前綴上的鍵值非遞減,而且每個鍵值都不大於每個非 null 的剩餘表頭的鍵值。(iii) left 與 right 指向兩個輸入未被觸動的後綴,兩者仍互不相交,也仍已排序。
初始時沒有選取任何節點,tail 是 dummy,兩個後綴就是整個輸入。設迴圈體執行一次。由於各後綴已排序,兩個表頭中較小者不大於兩個後綴中所有剩餘的鍵值。無論選了哪一個表頭,被選的都是那個較小者(相等時取左),所以把它接上便保持 (ii)。被選中的輸入指標先行推進,因此下一次迭代覆寫 tail.next 時,該後綴的其餘部分不會丟失;(i) 與 (iii) 得以保持。
當其中一個輸入指標為 null 時迴圈結束。每次迭代移走一個節點,而另一個鏈表在該次迭代中非空,所以另一個後綴至少剩下一個節點。該後綴已排序,由 (ii) 其鍵值不小於前綴中的每個鍵值,而且因輸入有限且無環,它以 null 結尾。一次賦值便把它接上,所以結果以 null 結尾;節點是逐一從互不相交的鏈表移出的,所以每個節點只出現一次。每個輸入的節點都從前端取走,所以各輸入保持其次序。
關於穩定性:只有當 嚴格成立時,才會選右表頭而不選左表頭。左後綴已排序,所以此時沒有剩餘的左節點與該右節點鍵值相等。因此鍵值為 的每個左節點,都先於任何鍵值為 的右節點被選取。
當 時至多迭代 次,每次做 的工作,最後的接駁也一樣。額外儲存只有 dummy、tail、chosen,為 。
證明透視
不變量必須描述連結,而不只是鍵值
這個不變量同時談到三件事:輸出前綴的鍵值、前綴上的節點身分,以及兩個輸入後綴的狀態。每個假設只在一處使用。輸入已排序,只用來得知較小的表頭比自己那個鏈表裏所有剩餘節點都小。互不相交,用來說明每次迭代都恰好從一個後綴移走一個節點,並使兩個後綴保持互不相交。有限與無環只在最後使用,以得知被接上的後綴以 null 結尾。
唯一微妙之處是覆寫。下一次迭代會賦值 tail.next,取代原本通向被選節點所在鏈表其餘部分的指標。這沒有問題,因為輸入指標已在同一次迭代中推進,後繼節點已經保存。
當其中一個表頭為 null 時,論證便完結:不變量已說明前綴已排序,且不大於所有剩餘節點,所以剩餘後綴可以整段接上,無須再作比較。
這些假設在實際中很容易被違反。
反例模式
共用節點使合併產生環
設 left 為 1a -> x,right 為 2c -> x,其中 x 是同一個鍵值為 5 的節點,且 x.next 為 null。兩個鏈表共用節點 x。迴圈先選 1a(因 ),再選 2c(因 ),此時 left 與 right 都等於 x。現在 ,所以 chosen = x、left = x.next = null、tail.next = x,迴圈結束。最後的分支設 tail.next = right,即 x,於是 x.next = x。輸出是 1a -> 2c -> x -> x -> ...,永遠到不了 null。
失敗源於輸入鏈表互不相交這個假設:共用節點從兩邊各被選取一次,第二次選取把它連回自身。修補辦法是遵守這個前置條件,而不是修補迴圈。
常見錯誤
(在合併中使用嚴格比較)
若迴圈改用 left.key < right.key 而不是 left.key <= right.key,鍵值相等時會先取右鏈表的節點。左為 2a、右為 2c 時,輸出是 2c -> 2a。有序性沒有改變,但排序不再穩定。
例題 18.1.3
(兩個鏈表之間有相等鍵值的合併)
設左鏈表為 1a -> 3a -> 3b,右鏈表為 2c -> 3c -> 5c,其中字母用以識別節點。先選 1a(1 對 2),再選 2c(3 對 2)。接著兩個表頭是 3a 與 3c,鍵值相等,所以選左節點 3a;然後 3b 對 3c 又是相等,所以選 3b。左鏈表此時已空,剩餘的 3c -> 5c 不經比較直接接上。最終的鏈為 1a -> 2c -> 3a -> 3b -> 3c -> 5c -> null。共作 4 次比較,不超過 。
數值排序正確,六個節點身分各出現一次,而相等鍵值保持左先於右的次序。穩定性所表達的,比單純傳回鍵值序列更多。
2. 分割與排序
定義 18.1.4
(快慢指標分割)
鏈表合併排序把含 個節點的鏈表分割成兩個較短的連續鏈表,分別遞歸排序,然後把它們合併。分割使用一個從鏈表頭開始的慢指標,以及一個從第二個節點開始的快指標。當 fast 與 fast.next 均非 null 時,慢指標前進一步,快指標前進兩步。保存 right = slow.next,然後設 slow.next = null。左半部從原鏈表頭到 slow,右半部從 right 開始。空鏈表及單一節點鏈表是基本情況。
定理 18.1.5
(分割、鏈表合併排序的正確性與成本)
當 時,分割產生兩個互不相交、以 null 結尾的鏈表,節點數分別為 與 ,保持原有次序,合起來恰好包含每個節點一次。鏈表合併排序傳回同樣的 個節點,按鍵值非遞減次序排列,而且是穩定的。它需時 ,遞歸堆疊為 ,並重用鏈表節點。
證明
(計算指標步數,再對長度歸納)
把節點編號為 。迴圈迭代 次後,slow 在位置 ,fast 在位置 ,超出 的位置表示 null。迴圈恰在 fast 與 fast.next 都存在,即 時再執行一次。因此它在 次迭代後停止,此時 slow 在位置 。在 slow 之後截斷,左鏈表有 個節點,右鏈表有 個節點,因為 。兩者都嚴格短於 。
對長度歸納。長度不超過一的鏈表已排序。當 時,兩半都較短、互不相交、有限且無環,所以由歸納假設,兩次遞歸調用傳回已排序、且恰好由各自節點組成的鏈表。合併定理適用,給出包含全部 個節點的已排序鏈表。
關於穩定性:設鍵值相等的節點 在輸入中先於 。若兩者在同一半,遞歸調用與合併都保持它們的次序。否則 在左半、 在右半,而合併把左節點排在右節點之前。
關於成本:在遞歸深度 ,各子鏈表劃分這 個節點,每個至多有 個節點。分割含 個節點的鏈表約需 步,合併需 ,所以每一層花費 。當 時,子鏈表只含一個節點,所以有 層、時間為 。遞歸堆疊每層一個框,共 。
概念視角結構
穩定性是鍵值與位置上的次序
把節點按輸入次序編號為 。穩定排序所返回的節點次序,恰好是按數對 的字典序遞增排列。這些數對全都不同,所以這個次序是唯一的。對 4a -> 1b -> 3c -> 2d,數對為 ,排序後得到 1b, 2d, 3c, 4a。每次合併在鍵值相等時優先取左邊的節點,就是在遵守位置這一分量。
例題 18.1.6
(分割並排序四個節點)
對於 4a -> 1b -> 3c -> 2d,分割得到 [4a,1b] 和 [3c,2d]。把兩半排序得到 [1b,4a] 和 [2d,3c];合併時比較 1 與 2(取 1b)、4 與 2(取 2d)、4 與 3(取 3c),再接上 4a,得到 [1b,2d,3c,4a]。由於子鏈表愈來愈短,算法必定終止。以歸納法而言,每個傳回的一半都已排序,並恰好包含其原有節點;合併的論證隨即給出整個鏈表的結果。由於分割保持輸入的連續次序,而相等情況以左半部優先處理,整個排序是穩定的。
例題 18.1.7
(邊界情況:空輸入與奇數長度)
若 left 為 null 而 right 為 2a -> 4a,迴圈體不執行。因為 left 為 null,最後的分支設 tail.next = right,函數傳回 dummy.next,即 2a。若兩個輸入都是 null,同一分支把 dummy.next 設為 null,結果為 null。
現在分割 5a -> 4b -> 3c -> 2d -> 1e。慢指標從 5a 出發,快指標從 4b 出發。fast 與 fast.next 都存在,所以慢指標移到 4b,快指標移到 2d。兩者再次都存在(2d 與 1e),所以慢指標移到 3c,快指標前進兩個節點成為 null。迴圈停止。保存 right = 2d 並截斷 3c.next,得到 5a -> 4b -> 3c 與 2d -> 1e,大小為 與 ,與定理的預測一致。必須先保存 right 再截斷,下一個方塊會說明原因。
常見錯誤
(在保存右半部之前先截斷鏈表)
若分割先設 slow.next = null,再讀取 right = slow.next,讀到的是 null。對於 4a -> 1b -> 3c -> 2d,慢指標停在 1b;先截斷會令 right 為 null,節點 3c 與 2d 便丟失了。
合併本身只使用常數個輔助指標,所以上面的堆疊界只來自排序的遞歸。另一種每次調用只遞歸合併一個節點的實作,其合併堆疊深度可能需要 O(n),所以其空間方面的論斷必須另行分析。
3. 習題與解答
快速檢查
(合併左鏈表 2a -> 2b 與右鏈表 2c。給出結果及鍵值比較次數。)
相等時一律偏向左鏈表。
解答 · 答案
表頭 2a 與 2c 相等,所以選 2a。接著 2b 對 2c 又相等,所以選 2b。左鏈表已空,接上 2c。結果是 2a -> 2b -> 2c,共作 2 次比較。
快速檢查
(合併 1a -> 3a -> 5a 與 2b -> 4b 要作多少次鍵值比較?對長度為 3 與 2 的鏈表,最多可以有多少次?)
數一數迭代到其中一個鏈表為空為止的次數。
解答 · 答案
比較依次是 1 對 2、3 對 2、3 對 4、5 對 4,共 4 次,之後右鏈表已空,接上 5a。一般的界是 ,所以這個輸入達到最大值。
快速檢查
(用快慢指標分割六個節點的鏈表 n1 -> n2 -> n3 -> n4 -> n5 -> n6。兩半各含哪些節點?)
追蹤慢指標與快指標的位置,直至迴圈條件不成立。
解答 · 答案
慢指標從 n1 出發,快指標從 n2 出發。fast 與 fast.next 都存在,所以慢指標移到 n2,快指標移到 n4。兩者再次存在,所以慢指標移到 n3,快指標移到 n6。此時 fast.next 為 null,迴圈停止。右半部從 n4 開始,所以兩半是 n1 -> n2 -> n3 與 n4 -> n5 -> n6,大小都是 。
快速檢查
(為甚麼分割必須在 slow 處截斷,而不能只記錄 right = slow.next?)
想一想對左半部的遞歸調用看到的鏈表是否更短。
解答 · 答案
若不截斷,左半部仍連到右半部,兩個鏈表並不互不相交,左鏈表也沒有變短。對兩個節點的鏈表,左側調用會再次收到兩個節點,遞歸永遠到不了基本情況。