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