單向鏈結結構未必以 null 結束:一條出錯的連結可能指回較早的節點,令列印迴圈永不終止。Floyd 的慢指標與快指標方法只需常數額外指標儲存便能偵測環,並可找出環的入口。此方法適用於有限且穩定的結構,其中每個節點只有一個 next 指標;它不要求節點的值互不相同。比較的是節點身分,而不是節點儲存的值。
環偵測是鏈表追蹤的延伸應用。
定義 2.2.1
(尾長與環長)
從 head 沿 next 前進。若序列到達 null,結構為無環。否則某個節點被經過兩次,入口就是首個被經過兩次的節點。設 為由 head 到入口的連結數目(尾長), 為由入口開始的環所含的節點數。從 head 可到達的 個節點全部互不相同。環問題的輸入是 head:若可到達環,傳回環上的一個節點,否則傳回 null。
1. 先講安全的偵測,再講證明
假設從 head 沿 next 前進,最終會到達 null 或重複經過某個節點。利用程式語言中短路求值的 and,算法如下:
slow = head
fast = head
while fast != null and fast.next != null:
slow = slow.next
fast = fast.next.next
if slow == fast: # compare node identities
return slow # a meeting node, not necessarily the entry
return null # no reachable cycle
迴圈條件必須先檢查 fast,才可存取 fast.next。更新步驟是安全的:當 fast.next 存在時,即使 fast.next.next 是 null,它仍是一個有效的指標值。在無環路徑上,slow 落後於 fast,此時必定非 null;在有環路徑上,兩個指標都不會到達 null。若 head 為 null,迴圈不會執行。若只有一個節點的串列以 null 結束,迴圈同樣不會執行。自環則會在第一次迭代時產生相遇。在移動之後才檢查是否相等,可避免初始的相等關係 slow == fast == head 令非空的無環串列被誤判為有環。
若串列到達 null,快指標最多只會經過有限個節點,迴圈條件最終必定不成立。在這樣的路徑上,沒有節點會被經過兩次,因此慢指標與快指標在各自走了不相等的正數步之後,不可能在某個非 null 節點相遇。若存在環,兩個指標最終都會進入環內;下一節將說明為何它們之後必定相遇。
常見錯誤
(比較儲存的值而不是節點身分)
取五個節點的無環串列 null,各節點的值為 。第一次迭代後兩個指標在 和 ,第二次迭代後在 和 。這兩個節點的值都是 ,所以按值比較會在沒有環的串列中報告有環。 與 的身分不同,身分比較便正確地繼續,隨後由迴圈條件在 null 處停止。
常見錯誤
(在第一次移動之前就檢查相遇)
若把相等檢查放在指標移動之前,對每個非空串列,一開始 slow == fast(兩者都等於 head)就成立,於是每個串列都會被報告為有環。對無環串列 null,正確的迴圈只迭代一次,此時 slow 在 、fast 為 null,並傳回 null。因此最早可能的相遇時間是 ,也因此在 時首次相遇在 而不是 。
2. 用距離解釋相遇點和入口
經過 次迴圈迭代後,慢指標走了 條連結,快指標走了 條。當 時,兩者都在環內。以環入口為基準,它們的位置分別是模 的 和 。
概念視角幾何
在圓周上追趕
兩個指標都進入環之後,把間距定義為快指標領先慢指標的連結數,並取模 。每次迭代,快指標走兩條連結,慢指標走一條,所以間距恰好增加一。在第 次迭代,間距是 ;間距回到零時,兩個指標恰好相遇。
定理 2.2.2
(偵測與相遇時間)
對有限的無環結構,迴圈以 null 結束。若可到達環,尾長為 、環長為 ,則迴圈恰好在 次迭代後傳回環上一個節點,其中 是不小於 的最小正的 倍數。特別地,,所以偵測需要 時間和 指標儲存。
證明
(兩個指標恰在環長的倍數時重合)
設 。若 ,慢指標仍在尾部、入口之前的節點,而尾部的每個節點都不同於環上的每個節點,所以若快指標在環內,兩者不可能相等。若快指標也在尾部,它離 head 有 條連結,慢指標只有 條,而 ,所以兩者是不同節點。因此在 之前不會相遇。
當 ,兩個指標都在環內,以入口為基準,位置分別是模 的 和 。兩者重合當且僅當 ,即
在 或之後必定存在 的某個正倍數,因此偵測必定終止,首次相遇的時間就是最小的這樣的倍數。若 ,它是 而不是零,因為算法在移動之後才作檢查。這個倍數至多是 : 時等於 ; 時, 的倍數彼此相隔 ,所以有一個落在 內。因此工作量是 ,只儲存兩個指標。
定理 2.2.3
(找出入口)
設指標在 次迭代後相遇,。把其中一個指標留在相遇節點,並把另一個重設到 head。若兩者每步前進一條連結,它們恰好在 步後首次相遇,相遇的節點就是入口。
證明
(相遇節點距入口在環內還差 步)
相遇時慢指標走了 條連結,所以相遇節點相對於入口的位置是 。再走 步,它的位置是 ,即入口。被重設到 head 的指標恰好走 條連結到達入口。因此兩者在 步後都在入口。
它們不可能更早相遇。在走完 步之前,被重設的指標仍在環外,而另一個指標始終在環內,尾部節點不同於環上任何節點。當 時,兩者一開始已在入口,不需要額外移動。
證明透視
為何相遇節點能指向入口
證明依賴一個量,就是尾長 。條件 來自相遇規則,它把相遇位置變成模 的 ,這只取決於尾長。所以從相遇節點再走 步會落在入口,而從 head 走同樣 步也落在入口。第二階段兩個指標必須等速:否則兩次行走到達時便不會都是 條連結。首次相遇的唯一性來自尾部在環之外。注意相遇節點本身並不直接說明入口在哪裏:說明入口的是兩段長度相同的行走,下面的追蹤便是一例。
3. 完整追蹤例子
例題 2.2.4
(兩個節點的尾部與四個節點的環)
設 A → B → C → D → E → F → C。這裏 ,。記錄每次偵測迭代後的指標位置:
| 迭代 | slow | fast |
|---|---|---|
| 1 | B | C |
| 2 | C | E |
| 3 | D | C |
| 4 | E | E |
相遇點是 E,而不是 C。把一個指標重設到 A,另一個留在 E。走一步後它們分別在 B,F;走兩步後在 C,C,即入口。若要另外量度環的長度,可把一個指標固定在 C,再沿 next 前進直至回到 C,數得四條連結。單憑任意一個相遇節點的值或位址推斷 是不正確的。
反例模式
相遇節點就是入口
一個誘人的說法是:slow 與 fast 相遇的節點就是環的第一個節點。在上面的追蹤中,相遇節點是 E,入口卻是 C,在環內相差兩條連結。事實上,相遇位置相對於入口是模 的 ,即 ,它非零是因為 不是 的倍數。只有當 整除 (例如 )時,這個說法才成立。修正的程序是把一個指標重設到 head,兩者每步前進一條連結,第二次相遇的節點就是入口。
例題 2.2.5
(環從頭節點開始)
設 A → B → C → A,所以 、。兩個指標都從 A 開始:
| 迭代 | slow | fast |
|---|---|---|
| 1 | B | C |
| 2 | C | B |
| 3 | A | A |
首次相遇在第 次迭代,節點是入口 A;迭代次數是 而不是 ,因為相等只在移動之後檢查。由於 ,兩個指標本來就在入口上,重設階段不需要任何步驟。對自環 A → A,第一次迭代後 slow 與 fast 都在 A:相遇在 。
例題 2.2.6
(無環串列與 null 檢查)
空串列的 head 為 null,迴圈不會開始,傳回 null。對 A → null,迴圈條件 fast.next != null 立即不成立,傳回 null。對 A → B → null,第一次迭代把 slow 移到 B、fast 移到 null;slow == fast 為假(B 不是 null),之後迴圈條件不成立。對 A → B → C → null,第一次迭代得 B 和 C,迴圈條件 fast.next != null 在 C 處不成立。每種情形下算法都傳回 null,而不會解參照 null 指標,因為先測試 fast 才測試 fast.next。
4. 若題目要求斷開環
找到入口後,由入口開始放一個指標並向前推進,直至它的 next 指回入口。這個節點就是環中的前驅節點;只把它的 next 改為 null。對於自環,前驅節點就是入口本身。原本可到達的全部 個節點仍然各恰好可到達一次,並保持原來首次經過的次序。只有當調用者擁有這些連結的控制權,並明確想得到一條線性串列時,才適合作出這種修改。偵測及尋找入口的程序本身不會修改任何連結。
檢查清單。 說明結構有限且穩定的假設,並比較節點身分。在解參照之前先檢查 null。區分相遇點與入口,用模位置解釋重設步驟的理據,並在陳述時間複雜度時同時計算非環前綴和環本身。不要聲稱單次執行能證明一個連結會被並行修改的結構的行為。
習題與解答
快速檢查
(對 A → B → C → D → B 追蹤 Floyd 偵測。給出 和 、相遇節點、相遇的迭代次序,以及重設階段找到的節點。)
解答 · 答案
入口是 B,所以 、(環為 B, C, D)。各次迭代後的指標:第 1 次,slow B、fast C;第 2 次,slow C、fast B;第 3 次,slow D、fast D。它們在第 次迭代於 D 相遇,這是不小於 的最小正的 的倍數。把一個指標重設到 A,另一個留在 D。走一步後兩者都在 B,所以重設階段在 步後找到入口 B。
快速檢查
(某串列的尾長 ,環長 。指標在第幾次迭代相遇?相對於入口在哪個位置?)
解答 · 答案
相遇的迭代是不小於 的最小正的 的倍數,即 。慢指標走了 條連結,所以它在入口之後 個節點處。這與 一致。其後重設階段正好需要 步到達入口。
快速檢查
(在 A → B → C → D → B 上,Floyd 算法找到入口 B 之後,如何斷開環使串列成為線性?結果是甚麼?)
解答 · 答案
從 B 放一個指標並向前推進,直至它的 next 是 B。B.next 是 C,C.next 是 D,D.next 是 B,所以 D 是環中的前驅節點。把 D.next 設為 null,得到線性串列 A → B → C → D → null,四個節點仍然各恰好可到達一次。