很多同學在接觸“快慢指針找環(huán)”這個經(jīng)典問題時都是靠背代碼過關的。第一階段慢指針每次走一步快指針每次走兩步如果兩個指針相遇了說明鏈表有環(huán)第二階段把某個指針重置到鏈表頭再讓兩個指針一步一步走第二次相遇的位置就是環(huán)入口。代碼兩三行就寫完了但真被問到“為什么要重置重置后為什么一定會相遇到入口”的時候很多人就卡住了。我自己在面試別人時這個問題問過很多次能完整推導出來的人確實不多。這篇文章準備專門把“重置快/慢指針”這個動作講透同時把“找環(huán)”“找入口”“算環(huán)長”“找中間節(jié)點”“找倒數(shù)第k個節(jié)點”這幾個容易混的場景放在一起辨析。如果你正在準備算法面試或者工作中要處理循環(huán)鏈表、環(huán)型依賴這類結構這篇應該能幫你少走不少彎路。1. 第一階段判斷有沒有環(huán)這一步根本不涉及重置1.1 快慢指針的移動規(guī)則與基礎代碼先來看最基礎的一段代碼。這里的 head 是鏈表的頭節(jié)點slow 和 fast 都從 head 出發(fā)def has_cycle(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False這段代碼里有兩個細節(jié)值得停下來想一想。第一fast 為什么可以被當成普通節(jié)點來訪問兩次 next因為循環(huán)條件里已經(jīng)保證了 fast 本身不為空、fast.next 也不為空所以 fast.next.next 不會因為 fast.next 為空而拋異常。第二如果鏈表沒有環(huán)循環(huán)會在 fast 或者 fast.next 為空的時候退出此時返回 False如果鏈表有環(huán)循環(huán)永遠不會因為 fast 走到末尾而退出唯一的退出方式就是 slow 和 fast 相遇然后返回 True。很多文章會把這一步稱為“龜兔賽跑”兔子跑得快烏龜跑得慢如果跑道是環(huán)形的兔子遲早會從后面追上烏龜如果跑道是直的兔子會先跑到終點。這個比喻非常直觀我也經(jīng)常用但要注意它只能解釋到“有環(huán)就一定會相遇”這一層還解釋不了“相遇點在哪里”以及“怎么從相遇點找入口”這兩個問題后面兩節(jié)會把這些補上。提示這里我特意讓 slow 和 fast 都從 head 出發(fā)。有些寫法會讓 fast 從 head.next 出發(fā)從“判斷有沒有環(huán)”的角度來說也能過但后面的入口推導會變得不那么直觀所以本文統(tǒng)一用都從 head 出發(fā)的寫法。1.2 為什么快指針每次走2步而不是3步或4步這是很多初學者會問的問題。為什么不選3步、4步其實核心只有一個詞相對速度?？熘羔樏看巫?步、慢指針每次走1步那么每一輪過去快指針比慢指針多走1步。在環(huán)上只要兩者之間有距離差這個距離差每輪就會穩(wěn)定地縮小1不存在“跨過去”的情況所以最多走完一圈的長度快指針一定能追上慢指針。如果把快指針改成每次走3步相對速度就變成了2。這會有兩個問題。第一追擊距離每輪縮小2當這個距離是奇數(shù)而環(huán)長是偶數(shù)的時候快指針可能會從慢指針“身邊”跨過去本來該追上的那一輪變成了超車于是需要再多繞一圈。第二從同余的角度看相對速度2和環(huán)周長如果不滿足特定關系還會出現(xiàn)永遠追不上的情況。舉個最簡單的例子環(huán)上只有兩個節(jié)點快指針落后1步每一次相對位置都會因為加2而對環(huán)長取模變成原地踏步兩個指針之間的距離永遠不變。所以經(jīng)典算法里選“快2慢1”不是隨便選的而是為了把相對速度控制在1讓數(shù)學性質最干凈。另一個被問得比較多的問題是為什么不能讓快指針每次走1步、慢指針不動因為如果慢指針停在一個鏈表上的非環(huán)節(jié)點快指針永遠都跑不到它那里即使慢指針停在環(huán)上也要求它恰好停在被快指針經(jīng)過的那個節(jié)點這種寫法沒有任何通用性。因此慢指針必須具備“自己也往前走”的能力快指針才能通過相對速度1去追它。1.3 無環(huán)與有環(huán)兩條完全不同的退出路徑這里要特別說明一下無環(huán)和成環(huán)時循環(huán)的退出差異因為這直接影響后面“是否該重置”的判斷。無環(huán)鏈表是單行道。fast 每輪走兩步它會先于 slow 到達鏈表的末尾。當 fast 指向 None、或者 fast.next 指向 None 時while 條件不成立循環(huán)自然結束。注意如果鏈表只有一個節(jié)點初始 fast 和 slow 都等于 headfast.next 是 None循環(huán)直接就退出了更不會發(fā)生一次移動。有環(huán)鏈表上不存在 None因為環(huán)里的節(jié)點永遠有下一跳。這時候 while 判空條件形同虛設循環(huán)只可能因為 break 或者 return 退出。所以在判斷是否有環(huán)的代碼里必須把“slow fast”放在循環(huán)體內判斷并且一旦滿足就立刻返回 True。如果寫成下面的錯誤版本while fast and fast.next: slow slow.next fast fast.next.next return slow fast在有環(huán)鏈表上會怎樣代碼根本走不到 return 那一行因為它在環(huán)里永遠不會退出直接變成死循環(huán)。這種錯誤在初學者代碼里出現(xiàn)頻率很高值得留意。2. 重置快/慢指針的核心邏輯為什么重置后能在入口相遇2.1 重置操作與兩種等價寫法第一階段只能告訴我們“有環(huán)”但環(huán)入口在哪里并不知道。要找到入口就需要第二步重置指針。最經(jīng)典的寫法是重置慢指針到鏈表頭快指針留在相遇點不再“賽跑”然后兩個指針都改成每次走1步直到兩者再次相等那個位置就是環(huán)入口。def detect_cycle_start(head): slow head fast head has_cycle False while fast and fast.next: slow slow.next fast fast.next.next if slow fast: has_cycle True break if not has_cycle: return None slow head # 重置慢指針到鏈表頭 while slow ! fast: # 兩個指針都每次走1步 slow slow.next fast fast.next return slow細心的讀者會發(fā)現(xiàn)這里重置的是 slow。如果把第二段改成把 fast 重置到鏈表頭、slow 留在相遇點效果完全一樣fast head while slow ! fast: slow slow.next fast fast.next return slow為什么兩種寫法都能得到入口因為第二階段真正要求的不是一個“固定的指針”回到鏈表頭而是“兩個指針中有一個回到鏈表頭另一個保持在相遇點”。至于具體是哪個指針回到頭部不影響任何推導。很多題解里一會兒重置慢指針、一會兒重置快指針把初學者搞暈了其實它們只是同一件事的兩種寫法。核心點是第二階段的起點是一頭一相遇點速度和步長都是1。注意第二階段絕對不能繼續(xù)保持“快2慢1”的速度。原因很簡單快指針如果保持每次走2步它的追擊邏輯又會啟動兩個人不一定在入口處相遇甚至可能再次錯過和追趕把問題復雜化。第二階段追求的是“兩個步長為1的指針從兩個固定起點出發(fā)在環(huán)入口精確會合”。2.2 數(shù)學推導相遇點與入口的距離關系要理解“為什么重置后能在入口相遇”需要一點簡單的代數(shù)。定義三個量L鏈表頭到環(huán)入口需要經(jīng)過的節(jié)點數(shù)也就是從頭節(jié)點走 L 步到達入口節(jié)點x環(huán)入口到第一階段相遇點需要經(jīng)過的節(jié)點數(shù)也就是從入口節(jié)點走 x 步到達相遇點C環(huán)的周長環(huán)上的節(jié)點總數(shù)。慢指針從鏈表頭出發(fā)在相遇時總共走了 L x 步。為什么慢指針只走不到一圈因為當慢指針進入環(huán)時快指針已經(jīng)至少領先它一步慢指針在環(huán)上還沒走完一圈就會被追上這個結論可以直接用?？熘羔槒逆湵眍^出發(fā)在相遇時總共走了 L x k*C 步其中 k 是快指針相對慢指針多繞的整圈數(shù)k 至少為1。又因為快指針速度是慢指針的兩倍所以L x k*C 2 * (L x)化簡得到L k*C - x這個式子就是整道題的核心。它說的是鏈表頭到環(huán)入口的距離 L等于若干倍環(huán)周長減去“入口到相遇點”的距離 x。換句話說L (k - 1)*C (C - x)其中 C - x 是從相遇點繼續(xù)往前走到入口的距離。于是如果一個指針站在鏈表頭另一個指針站在相遇點兩人都每次走1步走 L 步后鏈表頭的指針到了入口相遇點的指針往前走 L 步相當于先走 C - x 到入口再整圈整圈地繞 (k - 1) 圈最終也停在入口。兩者必然在入口處相遇。這就是第二階段能精確找到入口的根本原因。這里有一個容易想不通的細節(jié)快指針在相遇時到底多繞了多少圈k 取幾其實不重要因為等式兩邊已經(jīng)把“圈數(shù)”消掉了。不管 k 是1、2還是更大的數(shù)L 和 C - x 之間始終存在這種“差一個環(huán)長整數(shù)倍”的關系所以重置后走 L 步的結論對所有 k 都成立。2.3 用真實例子跟蹤一遍指針只看公式可能有點抽象我們來手動跑一個鏈表。構造一個帶環(huán)鏈表1 - 2 - 3 - 4 - 5 - 6 - 3。它的入口是節(jié)點3L 等于2從節(jié)點1走兩步到節(jié)點3環(huán)長 C 等于43 - 4 - 5 - 6 - 3。第一階段從 slow fast 節(jié)點1開始每一輪兩個指針的移動情況如下輪次slow位置fast位置初始11第1輪23第2輪35第3輪43第4輪55第4輪結束slow 和 fast 在節(jié)點5相遇。入口是節(jié)點3從入口到相遇點需要走2步3 - 4 - 5所以 x 2。C - x 4 - 2 2正好等于 L。現(xiàn)在進入第二階段把 slow 重置到節(jié)點1fast 留在節(jié)點5。輪次slow位置fast位置初始15第1輪26第2輪33第2輪結束時兩者在節(jié)點3相遇也就是環(huán)入口。直覺上看就是“從鏈表頭走 L 步”和“從相遇點走 L 步等效于 C - x”剛好在入口處碰頭。這個例子非常有代表性因為 L 恰好等于 C - x更容易看出對稱性。換個 L 不等于 C - x 的例子結果也一樣只是多繞幾圈再碰頭。2.4 第二階段最容易犯的錯誤忘記把速度改成1步說句實話我在代碼評審里見過最多的錯誤不是第一階段寫不對而是第二階段把重置做對了速度卻忘了改。比如有人寫了slow head while slow ! fast: slow slow.next fast fast.next.next # 錯第二階段還在用2倍速這個版本在部分鏈表上可能碰巧能算對但大概率會在入口處錯過或者陷入死循環(huán)。因為此時 fast 仍然保持“每輪追上一步”的追擊狀態(tài)它的行為不再滿足上面那條 L k*C - x 的推導前提。第二階段的每一步都必須把兩個指針放在同一個速度上這一點值得在代碼旁邊寫一行注釋提醒自己這里不是龜兔賽跑了現(xiàn)在是兩只烏龜在走。3. 場景辨析哪些要重置哪些不要3.1 僅判斷是否存在環(huán)如果需求只是“這鏈表有沒有環(huán)”第一階段跑完就結束了完全不需要第二階段。很多人會習慣性地把“探測環(huán)”和“找入口”寫進同一個函數(shù)這是沒必要的。判斷有環(huán)的代碼只需要返回布爾值在 slow fast 成立時返回 True循環(huán)正常退出時返回 False干凈利落。這個場景是最基礎的送分題不需要引入重置邏輯。3.2 定位環(huán)入口節(jié)點定位入口是“必須重置”的典型場景。這時候不僅要返回“有環(huán)”還要返回一個具體的節(jié)點引用。重置以后兩個指針第二次相遇的節(jié)點就是入口。比如做循環(huán)引用分析、修復污染鏈表、或者要在入口處打斷環(huán)都需要這個返回值。這個場景也是本文標題里“重置”一詞最直接的落點。3.3 計算環(huán)的長度計算環(huán)長有兩種做法都不需要重置到鏈表頭。第一種做法是先找到入口然后從入口節(jié)點出發(fā)每次走一步用計數(shù)器記錄走了多少步重新回到入口這個步數(shù)就是環(huán)長 C。第二種做法是在第一階段相遇后讓其中一個指針保持在相遇點另一個繼續(xù)走等它再次回到相遇點時走的步數(shù)也正好是一個環(huán)長。這里有一個很有意思的小點從環(huán)上任意一個節(jié)點出發(fā)走回同一個節(jié)點走的步數(shù)都是一樣的都等于環(huán)長。所以“計算環(huán)長度”這個場景關心的是 C而不是入口位置。你完全可以在第一階段相遇點直接開始計數(shù)省去第二階段的入口推導。但如果你的需求既要入口又要長度那就先做第二階段拿入口再數(shù)一圈拿長度兩條路徑是串行關系。3.4 尋找鏈表中間節(jié)點快慢指針的經(jīng)典應用之一是找鏈表中間節(jié)點。同樣是 slow 每次1步、fast 每次2步但判斷的是“快指針是否到達尾部”。當鏈表長度是奇數(shù)時fast 會落在最后一個節(jié)點上slow 正好落在中間節(jié)點當鏈表長度是偶數(shù)時fast 會落在 None 上slow 落在兩個中間節(jié)點中的第二個。這個場景和找環(huán)最明顯的區(qū)別是不需要第二階段不需要重置連環(huán)的存在都不關心。如果鏈表里有環(huán)還去找中間節(jié)點邏輯會完全跑偏所以使用前得先確認鏈表是無環(huán)的。這個場景最有價值的衍生應用是回文鏈表判斷。先用快慢指針找到中間節(jié)點再把后半段反轉最后逐節(jié)點對比。它和“找環(huán)”雖然都叫快慢指針但一個服務于對稱性校驗一個服務于環(huán)結構分析理念完全不同。3.5 尋找倒數(shù)第k個節(jié)點“倒數(shù)第k個節(jié)點”也會用雙指針但這里的雙指針初始并不是“速度差”而是“偏移差”。具體做法是讓 fast 先走 k 步然后 fast 和 slow 一起每次走1步。當 fast 走到鏈表末尾 None 時slow 正好指向倒數(shù)第k個節(jié)點。這個場景經(jīng)常被誤稱為快慢指針但嚴格來說它的兩個指針速度相同只是出發(fā)位置不同。它和“找環(huán)”的辨析點在于如果題目里說“重置指針”請你先確認這是“相遇后重置”還是“出發(fā)前讓一個指針先走k步”。后者跟環(huán)入口沒有一點關系只是因為某種原因也叫“雙指針技巧”。其實原理很簡單先走 k 步相當于讓兩個指針對齊一個長度差剩下就變成“找鏈表末尾的第k個位置”的線性問題。3.6 兩個鏈表找交點的“換路”不是快慢指針還有一個更容易混淆的場景是“兩個鏈表找交點”。這類題的常見做法是兩個指針分別從兩個鏈表頭出發(fā)速度都是1步當某個指針走到鏈表尾部時跳到另一個鏈表的頭部繼續(xù)走。如果兩個鏈表相交它們會在交點相遇如果不相交它們會同時走到尾部。這個技巧看代碼很像“重置指針”指針 A 走到頭后重置到鏈表 B 的頭指針 B 走到頭后重置到鏈表 A 的頭。但它和“找環(huán)第二步”的重置完全是兩碼事。找環(huán)第二步的重置是為了讓兩個指針在環(huán)入口會合依據(jù)的是相遇點與入口的距離關系而找交點的“換路”是為了構造長度對齊讓兩個指針同時走到交點。把這兩者放在一起看會發(fā)現(xiàn)“重置”這個詞在不同上下文里含義差異很大。理解到這一層才算真正把雙指針場景辨析清楚了。3.7 場景速查表我把上面幾個場景整理成一張表方便你復習時一眼定位。場景雙指針速度是否需要“相遇后重置”主要計算目標判斷鏈表是否有環(huán)快2慢1不需要是否存在環(huán)定位環(huán)入口第一階段快2慢1第二階段1:1必須入口節(jié)點計算環(huán)長度第一階段快2慢1之后1:1數(shù)圈不需要環(huán)周長 C找鏈表中間節(jié)點快2慢1不需要中間節(jié)點找倒數(shù)第k個節(jié)點1:1fast先走k步不需要出發(fā)前偏移倒數(shù)第k節(jié)點兩個鏈表找交點1:1走到底換路不需要走到頭換路交點節(jié)點4. 邊界條件與源碼級陷阱4.1 判空條件怎么寫才安全第一階段循環(huán)條件寫成 while fast and fast.next是最穩(wěn)妥的寫法。它同時保證了 fast 本身不為空以及 fast.next 不為空這樣 fast.next.next 才安全。如果寫成 while fast.next那么當快指針指向最后一個節(jié)點時循環(huán)還能進入但 fast.next.next 直接拋異常如果寫成 while fast那么當 fast 指向 None 時循環(huán)雖然不進入但在循環(huán)內 fast.next 可能拋異常。這里有一點容易被忽略有環(huán)鏈表上的循環(huán)并不會因為判空條件而退出所以判空條件只對無環(huán)情況有效。對帶環(huán)鏈表來說真正的出口必然是 slow fast 分支里的 return 或 break。兩個機制缺一不可。4.2 特殊鏈表形態(tài)逐個過我建議大家在寫完代碼后至少用下面幾種輸入自測一遍。第一種空鏈表 head 為 None第一階段循環(huán)直接跳過返回 None正確。第二種單節(jié)點無環(huán)鏈表 head.next 為 None也直接跳過循環(huán)返回 None正確。第三種單節(jié)點成環(huán) head.next head第一階段第一輪 slow 和 fast 都到 head兩者相遇重置 slow 回到 head 后第二階段第一次判斷就相等直接返回 head入口就是它自己正確。第四種雙節(jié)點成環(huán) 1 - 2 - 1手動跑一遍也能驗證結果。第五種入口就在鏈表頭的環(huán)比如 1 - 2 - 3 - 1此時 L 0第一階段會在入口節(jié)點相遇第二階段把 slow 重置到 head 后第一輪就是 slow fast直接返回 head。這五種形態(tài)雖然簡單但能暴露出大部分實現(xiàn)問題。提示如果本地沒有測試框架可以在鏈表節(jié)點類里加一個“節(jié)點ID”字段調試時打印每一步指針所在節(jié)點的ID能肉眼看出相遇位置和入口位置是否符合預期。4.3 常見錯誤實現(xiàn)診斷我把平時看到的錯誤實現(xiàn)歸納成四類你可以對照檢查自己有沒有踩過。第一類fast 從 head.next 出發(fā)。這種寫法判斷是否有環(huán)沒問題但第二階段如果仍然假設“從頭走 L 步到入口”推導需要微調。不是不能用但初學時建議統(tǒng)一從 head 出發(fā)減少心智負擔。第二類第二階段忘記把兩個指針都改成1步。前面專門講過這是重災區(qū)。癥狀是代碼在部分用例上結果正確在部分用例上死循環(huán)或者返回錯誤節(jié)點。第三類無環(huán)鏈表上調用第二階段。如果直接調用 detect_cycle_start而鏈表沒有環(huán)第一階段結束后 fast 可能已經(jīng)為 None此時不能進入第二階段。所以第二階段之前必須判斷是否有環(huán)沒環(huán)直接返回 None。第四類把節(jié)點值和節(jié)點引用混為一談。鏈表中可能存在重復值判斷相遇時比較的是“是否是同一個節(jié)點對象”而不是“節(jié)點值是否相等”。拿值相等來判環(huán)會在有重復值的鏈表上得到錯誤結論。4.4 一行日志快速定位問題排查這類問題時我習慣在循環(huán)里打印指針位置。比如在代碼里給節(jié)點加一個 index 字段然后打印 slow.index 和 fast.index。如果兩個 index 序列出現(xiàn)循環(huán)但不相等說明代碼路徑里可能有邏輯錯誤如果循環(huán)很久都很正常那大概率是第二階段速度沒有改回來。打印日志雖然土但比盯著代碼空想要高效得多。等確認邏輯正確后再把日志刪掉。5. 快慢指針在真實項目中的應用與選型參考5.1 環(huán)型結構檢測快慢指針最直接的業(yè)務映射是“檢測循環(huán)結構”。比如一些腳本引擎或規(guī)則引擎中節(jié)點之間存在引用關系如果配置不小心出現(xiàn)了循環(huán)引用遍歷時會進入死循環(huán)。此時可以用快慢指針在遍歷鏈路時檢測環(huán)。不過要注意真實的依賴關系往往是多分支的圖結構而不是簡單的鏈表?？炻羔樃m合“單鏈線性追蹤”場景一旦涉及多入度、多出度的圖更通用的是拓撲排序或染色法。鏈表的快慢指針是理解“環(huán)檢測”的最小模型但它不等于圖上的環(huán)檢測。5.2 環(huán)形緩沖與約瑟夫問題環(huán)形緩沖區(qū)、約瑟夫環(huán)這類問題和“環(huán)”天然相關。約瑟夫問題中人們繞著圈報數(shù)報到的節(jié)點出列本質上就是在環(huán)形鏈表上做刪除操作。這時候雙指針思路可以在快速跳過或定位時輔助但它和“檢測環(huán)”已經(jīng)是完全不同的任務。快慢指針的價值在于它用一個 O(1) 空間的辦法完成環(huán)結構分析而不是靠額外哈希表記錄訪問過的節(jié)點。5.3 為什么多數(shù)場景用HashSet就夠了很多工程場景下判斷鏈表是否有環(huán)其實用哈希表更省事遍歷節(jié)點把每個節(jié)點引用放進集合里如果發(fā)現(xiàn)某個節(jié)點已經(jīng)出現(xiàn)過說明有環(huán)。這個做法直觀、代碼簡單、容易調試代價是額外空間 O(n)。而快慢指針的獨特價值是空間復雜度只有 O(1)不需要任何額外容器。在內存受限的系統(tǒng)、或者面試考察“無額外空間”的約束下快慢指針是更合適的選擇。如果內存不緊張兩者都可以但你需要理解為什么面試官會問“你用 HashSet 做的話空間是 O(n)能不能優(yōu)化到 O(1)”這一層。5.4 面試時的表達順序建議最后給要面試的朋友一點建議。當被問到“如何找到鏈表環(huán)入口”時千萬不要只背代碼。一個比較推薦的表達順序是先說明第一階段如何判斷有環(huán)再說明為什么快指針選2步而不是3步相對速度1然后引入 L、x、C 三個量推導 L k*C - x最后解釋重置指針后兩個指針為什么在入口相遇。這樣一套講下來面試官會覺得你是真的理解而不是背題。如果直接被要求寫代碼可以在寫完之后口頭把邊界條件空鏈表、單節(jié)點、無環(huán)、入口在頭節(jié)點逐個過一遍這比沉默著寫完效果要好得多。我實際寫過很多次這個算法也幫不少同學改過相關代碼。說實話第一次學到第二階段的時候我也覺得很神奇憑什么一個指針回到頭另一個留在相遇點兩個人都走一步最后就正好在入口碰面直到自己拿紙筆畫了鏈表又跑了幾個例子才真正把那個等式印在腦子里。如果你現(xiàn)在也覺得這步很玄建議你先別急著背代碼拿個鏈表畫一畫把 L、x、C 標出來自己算一次比看十遍解析都管用。最后分享一個小技巧驗證環(huán)入口算法時構造一個“入口在鏈表頭”的環(huán)和一個“入口在中段”的環(huán)環(huán)長一奇一偶把兩種情況都測通了代碼基本就穩(wěn)了。