說實(shí)話LeetCode 141這道題我在面試中問過別人也被別人問過刷題網(wǎng)站上的題解翻了不下二十篇。環(huán)形鏈表、哈希表、快慢指針這幾個(gè)詞幾乎綁定在一起出現(xiàn)但真正能把為什么快慢指針是最優(yōu)解講透的人不多。多數(shù)人只是背下了快指針走兩步慢指針走一步相遇就是有環(huán)至于為什么一定會相遇、能不能走三步、哈希表和數(shù)組解法各自的問題在哪其實(shí)并沒有想清楚。這篇我就把這道題的三種主流思路拆開揉碎從原理到代碼再到面試話術(shù)一次說清。1. 題目本質(zhì)與常見誤解先搞清楚環(huán)到底是什么1.1 題目定義與輸入邊界題目描述很簡短給定一個(gè)鏈表的頭節(jié)點(diǎn)head判斷鏈表中是否有環(huán)。所謂有環(huán)指的是鏈表中某個(gè)節(jié)點(diǎn)的next指針指向了它之前出現(xiàn)過的某個(gè)節(jié)點(diǎn)導(dǎo)致鏈表在遍歷時(shí)永遠(yuǎn)走不到尾。這里有幾個(gè)容易忽略的輸入邊界空鏈表head為null直接返回false單節(jié)點(diǎn)鏈表只有一個(gè)節(jié)點(diǎn)且next為null無環(huán)單節(jié)點(diǎn)自環(huán)只有一個(gè)節(jié)點(diǎn)但next指向自己有環(huán)尾部節(jié)點(diǎn)指向鏈表中間的某個(gè)節(jié)點(diǎn)形成閉環(huán)。這些邊界雖然簡單但在筆試或面試的測試用例里都可能出現(xiàn)。我見過不少人在第一個(gè)if判斷里只處理了head null結(jié)果遇到單節(jié)點(diǎn)自環(huán)的用例直接訪問空指針。所以每次寫鏈表相關(guān)的題我習(xí)慣先問自己一句每個(gè)分支下head.next是否存在1.2 核心考點(diǎn)不是會不會做而是能不能想明白為什么這道題在面試中的定位很典型它屬于看起來簡單但能聊得很深的題型。函數(shù)的返回值只是true或false但面試官真正想考察的是三件事能否快速識別出哈希表方案并說出它的時(shí)間復(fù)雜度和空間復(fù)雜度能否進(jìn)一步想到不需要額外空間的方案能否解釋清楚快慢指針的數(shù)學(xué)原理而不是只背結(jié)論。第3點(diǎn)是最關(guān)鍵的。因?yàn)榄h(huán)形鏈表檢測不是一個(gè)孤立問題它是一個(gè)哲學(xué)層面的思想如何用有限的狀態(tài)判斷無限循環(huán)?？炻羔?、Floyd判圈算法、龜兔賽跑本質(zhì)都在解決這一類問題。理解了這一步后面做142題找環(huán)的入口、287題尋找重復(fù)數(shù)、202題快樂數(shù)都會順很多。1.3 一個(gè)容易踩的思維誤區(qū)很多初學(xué)者會把判斷是否有環(huán)和判斷是否有重復(fù)節(jié)點(diǎn)混為一談。注意鏈表節(jié)點(diǎn)的值可能重復(fù)但節(jié)點(diǎn)的引用是唯一的。用哈希表判斷時(shí)存儲的應(yīng)該是節(jié)點(diǎn)的引用Java中的ListNode對象、Python中的對象本身而不是節(jié)點(diǎn)的值。我當(dāng)初就犯過這個(gè)錯——用HashSetInteger存節(jié)點(diǎn)的val結(jié)果鏈表中兩個(gè)不同位置的值相同就直接誤判成有環(huán)了。鏈表節(jié)點(diǎn)的值重復(fù)在實(shí)際問題里非常常見所以這里必須是節(jié)點(diǎn)對象判重不能是值判重。2. 哈希表解法最樸素的正確解但細(xì)節(jié)決定成敗2.1 思路與實(shí)現(xiàn)思路一句話遍歷鏈表把每個(gè)節(jié)點(diǎn)存進(jìn)一個(gè)哈希集合如果當(dāng)前節(jié)點(diǎn)已經(jīng)在集合中出現(xiàn)過說明存在環(huán)如果遍歷到了null說明無環(huán)。以下是 Java 和 Python 的參考實(shí)現(xiàn)public boolean hasCycle(ListNode head) { SetListNode seen new HashSet(); ListNode cur head; while (cur ! null) { if (seen.contains(cur)) { return true; } seen.add(cur); cur cur.next; } return false; }def hasCycle(head: ListNode) - bool: seen set() cur head while cur: if cur in seen: return True seen.add(cur) cur cur.next return False代碼非常簡單跑一遍也一定能過。但注意這里的seen存的是節(jié)點(diǎn)對象。如果你用set()存了cur.val只要鏈表里有兩個(gè)節(jié)點(diǎn)的值相等就直接誤報(bào)有環(huán)。這道題的值域沒有限制所以這是必踩的坑。2.2 為什么哈希表是正確但不是最優(yōu)哈希表方案的時(shí)間復(fù)雜度是O(n)空間復(fù)雜度也是O(n)。它的效率其實(shí)很高單個(gè)節(jié)點(diǎn)的哈希查詢在平均情況下是O(1)。所以在工程代碼里如果你本來就允許使用額外存儲哈希表完全可以用。但它的問題在于面試官通常會追問一句能不能不用額外空間。這時(shí)候你如果只能說出哈希表面試深度就明顯不夠了。此外從算法競賽的角度看O(n)的空間在數(shù)據(jù)量很大的場景下可能觸及內(nèi)存限制而快慢指針的O(1)空間意味著無論鏈表多長額外內(nèi)存都是常數(shù)級別。我再來做一個(gè)直觀的對比用一張表格展示方案時(shí)間復(fù)雜度空間復(fù)雜度是否改變鏈表工程可用性哈希表O(n)O(n)否高數(shù)組記錄O(n)O(n)否中標(biāo)記節(jié)點(diǎn)O(n)O(1)是破壞數(shù)據(jù)低快慢指針O(n)O(1)否高這里你可能已經(jīng)注意到了數(shù)組記錄和標(biāo)記節(jié)點(diǎn)兩種方案我把它們單獨(dú)放到下一節(jié)講因?yàn)樗鼈兇_實(shí)有巧妙的切入角度也對應(yīng)了題目和熱搜詞里的數(shù)組。2.3 哈希表的冗余優(yōu)化思路哈希表的空間可以稍微壓縮一點(diǎn)如果你知道鏈表的長度上限n可以使用布爾數(shù)組visited以下標(biāo)表示節(jié)點(diǎn)地址的哈希值。但在語言層面比如 Java 中ListNode的默認(rèn)哈希值是基于內(nèi)存地址的直接轉(zhuǎn)成數(shù)組下標(biāo)并不方便。所以工程上更常見的還是用SetListNode簡單直接。一個(gè)小技巧是你在while循環(huán)里可以先把cur存下來再判斷也可以先判斷再存。上面的寫法是先判斷再加入邏輯清晰。實(shí)際面試時(shí)只要表達(dá)清楚集合中的節(jié)點(diǎn)都是已經(jīng)訪問過的即可不必糾結(jié)代碼順序。3. 數(shù)組解法與破壞性標(biāo)記可行但總有代價(jià)3.1 數(shù)組記錄法用順序存儲代替哈希表既然哈希表可以用那么用數(shù)組/列表記錄也自然可行。思路和哈希表幾乎一樣每訪問一個(gè)節(jié)點(diǎn)就把它追加到數(shù)組末尾每次前進(jìn)前先在數(shù)組中線性查找當(dāng)前節(jié)點(diǎn)是否已經(jīng)存在。def hasCycle(head: ListNode) - bool: arr [] cur head while cur: if cur in arr: return True arr.append(cur) cur cur.next return False這種寫法的時(shí)間復(fù)雜度是O(n^2)因?yàn)閏ur in arr在 Python 列表里是線性查找。所以它雖然理論上正確但在性能上遠(yuǎn)不如哈希表。數(shù)組解法更值得討論的地方在于如何讓查找更快——比如用數(shù)組下標(biāo)模擬哈希。3.2 基于值域假設(shè)的哈希數(shù)組如果題目給出節(jié)點(diǎn)值的范圍比如0 Node.val 10000那么你可以用一個(gè)大小的布爾數(shù)組seen [False] * 10001每次訪問節(jié)點(diǎn)時(shí)把seen[cur.val] True來實(shí)現(xiàn) O(1) 的判重。這種做法的空間是O(range)如果值域遠(yuǎn)大于節(jié)點(diǎn)數(shù)就不劃算如果值域小這是比哈希表更快的方式因?yàn)閿?shù)組內(nèi)存連續(xù)、緩存命中率高。但請你記住這種方法建立在節(jié)點(diǎn)值互不相同的隱含假設(shè)上。只要有重復(fù)值它就會誤判。所以我在刷題時(shí)只在項(xiàng)目代碼的特定場景下用這種值域哈希在 LeetCode 上基本不用。3.3 破壞性標(biāo)記法面試中的陷阱方案關(guān)于數(shù)組的熱搜詞里提到數(shù)組標(biāo)記我還想講一個(gè)經(jīng)常有人提出的思路修改節(jié)點(diǎn)結(jié)構(gòu)加一個(gè)visited字段或者遍歷時(shí)把節(jié)點(diǎn)的val改成一個(gè)特殊值比如Integer.MIN_VALUE。這樣如果后續(xù)再訪問到該值的節(jié)點(diǎn)就說明有環(huán)。public boolean hasCycle(ListNode head) { ListNode cur head; while (cur ! null) { if (cur.val Integer.MIN_VALUE) { return true; } cur.val Integer.MIN_VALUE; cur cur.next; } return false; }代碼確實(shí)能跑通空間也是 O(1)但這是一種臟方案。它在遍歷過程中破壞了鏈表中的原始數(shù)據(jù)假設(shè)有另一個(gè)線程同時(shí)讀這個(gè)鏈表數(shù)據(jù)就直接串了。在面試場景下除非面試官明確說可以不改變數(shù)據(jù)結(jié)構(gòu)否則我不建議主動提這種方法。如果提了也一定要主動說明它的副作用雖然空間是 O(1)但會修改原鏈表的數(shù)據(jù)實(shí)際工程中不推薦快慢指針才是無副作用的解法。這說明你有工程意識比單純背答案加分得多。3.4 為什么不推薦把數(shù)組方案作為面試首選數(shù)組解法對比哈希表的優(yōu)勢幾乎為零對比快慢指針在空間上又輸所以它是三種解法里最尷尬的。但我在刷題初期對哈希表不熟的時(shí)候曾經(jīng)就是用ArrayList硬寫。它的價(jià)值在于幫助初學(xué)者理解記錄已訪問節(jié)點(diǎn)的思想但真正面試時(shí)你至少要能在哈希表和快慢指針之間自由切換。一句話總結(jié)數(shù)組解法可以練習(xí)但不能作為最終答案輸出。4. 快慢指針為什么步長差一就能判定有環(huán)4.1 Floyd 判圈算法的直觀原理快慢指針也叫 Floyds Cycle Detection Algorithm弗洛伊德判圈算法。設(shè)置兩個(gè)指針slow和fast初始都指向head。slow每次走一步fast每次走兩步。如果鏈表無環(huán)fast會先到達(dá)null如果有環(huán)fast一定會在環(huán)里追上slow。很多人的疑問是為什么fast一定會追上slow而不是永遠(yuǎn)差一步我通常用操場跑圈來類比。兩個(gè)人在環(huán)形跑道上跑步一個(gè)速度快一個(gè)速度慢。只要跑道是環(huán)形的速度快的人一定會從后面追上速度慢的人。在這里fast比slow每次多走一步相當(dāng)于每過一個(gè)單位時(shí)間fast相對slow的距離就縮短 1。設(shè)環(huán)的長度為L那么一旦兩個(gè)指針都進(jìn)入環(huán)內(nèi)相對距離最大為L-1經(jīng)過最多L-1次循環(huán)fast必然追上slow。更嚴(yán)謹(jǐn)?shù)乇硎鲈O(shè)slow進(jìn)環(huán)時(shí)fast離它的距離為d0 d L每走一輪fast靠近slow一步因此最多d輪相遇。這就保證了不會出現(xiàn)永遠(yuǎn)差一步的巧合。4.2 完整實(shí)現(xiàn)代碼def hasCycle(head: ListNode) - bool: slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return Falsepublic boolean hasCycle(ListNode head) { if (head null || head.next null) { return false; } ListNode slow head; ListNode fast head.next; while (slow ! fast) { if (fast null || fast.next null) { return false; } slow slow.next; fast fast.next.next; } return true; }注意一個(gè)細(xì)節(jié)Java 版本我寫了fast head.next而不是fast head這是因?yàn)槿绻鹒ast初始也等于head在無環(huán)單節(jié)點(diǎn)鏈表上slow fast會直接返回true所以要么判空要么讓fast先走一步。兩種寫法都對但初學(xué)者往往在邊界上翻車。我推薦用slow head; fast head;然后在循環(huán)前判斷head和head.next是否為空這樣語義更統(tǒng)一。另一個(gè)容易忽略的坑是while (fast ! null fast.next ! null)的順序。在 Java 里如果寫成while (fast.next ! null fast ! null)當(dāng)fast為null時(shí)訪問fast.next會直接拋出空指針異常。邏輯運(yùn)算符有短路特性所以一定要把判空放在前面。4.3 步長為什么是 2不是 3 或更大很多人會想fast每次走 3 步、4 步是不是更快答案是不能保證相遇。由于鏈表是單向的指針在環(huán)內(nèi)只能沿著一個(gè)方向移動。當(dāng)fast每次走k步時(shí)它相對slow的收斂速度是k-1。如果k-1和環(huán)長L不互質(zhì)就可能出現(xiàn)永遠(yuǎn)錯位的情況。比如環(huán)長L3fast每次走 3 步相對速度是 2slow每走 1 步距離被拉近 2但 3 和 2 互質(zhì)不環(huán)內(nèi)距離的計(jì)算是模L的。當(dāng)k-1與L存在公因數(shù)時(shí)fast可以沿環(huán)反復(fù)跳過slow所在的位置。選擇步長 2 是最小、最簡單且能保證任何環(huán)長下收斂的組合。如果你細(xì)心會發(fā)現(xiàn)fast走 2 步還有一個(gè)好處它一定會在有限步內(nèi)到達(dá)null或進(jìn)入環(huán)復(fù)雜度是 O(n)不會被無限循環(huán)卡住。而如果選更大的步長代碼上判斷fast.next.next...next會產(chǎn)生大量空指針判斷寫起來也麻煩。4.4 復(fù)雜度與正確性分析快慢指針的時(shí)間復(fù)雜度是 O(n)空間復(fù)雜度 O(1)。每次循環(huán)slow走一步、fast走兩步相當(dāng)于每輪往前走 3 個(gè)節(jié)點(diǎn)。無環(huán)時(shí)經(jīng)過約 n/2 輪判斷到空節(jié)點(diǎn)有環(huán)時(shí)最多經(jīng)過一個(gè)鏈表長度加一個(gè)環(huán)長度的量級。實(shí)踐中它跑得比哈希表慢一點(diǎn)因?yàn)橐叩江h(huán)內(nèi)再相遇但空間優(yōu)勢是碾壓級的。正確性的關(guān)鍵其實(shí)只有兩點(diǎn)無環(huán)時(shí)fast必然先到null循環(huán)退出的條件覆蓋了無環(huán)情形有環(huán)時(shí)slow和fast都進(jìn)入環(huán)中且fast相對slow的步差為 1因此在有限步內(nèi)必然相遇。4.5 數(shù)組、哈希與快慢指針的取舍總結(jié)如果面試官問你還有沒有更好的方案你要能主動說哈希表方案空間 O(n)勝在實(shí)現(xiàn)簡單可讀性好快慢指針方案空間 O(1)是教科書級的原地判環(huán)方案且完全符合題目對空間的潛在要求數(shù)組方案一般作為思考過程提及即可不必展開。這道題的最優(yōu)解沒有懸念就是快慢指針。哈希表適合當(dāng)你還要記錄每個(gè)節(jié)點(diǎn)的訪問順序、做后續(xù)處理時(shí)使用如果只問是否有環(huán)快慢指針的時(shí)間與空間組合是最好的。5. 邊界條件與破環(huán)點(diǎn)從141到延伸題的思維跳躍5.1 特殊鏈表的完整測試用例我整理了一份可以直接用來驗(yàn)證代碼的邊界用例建議刷完手動跑一遍用例結(jié)構(gòu)預(yù)期結(jié)果空鏈表nullfalse單節(jié)點(diǎn)無環(huán)1 - nullfalse單節(jié)點(diǎn)自環(huán)1 - 自身true兩個(gè)節(jié)點(diǎn)閉環(huán)1 - 2 - 1(回到1)true長鏈尾接中間1 - 2 - 3 - 4 - 2true長鏈無環(huán)1 - 2 - 3 - 4 - nullfalse我自己在本地測試時(shí)常用一個(gè)createCycle輔助函數(shù)先構(gòu)造鏈表再讓尾節(jié)點(diǎn)指向索引k處。寫過一次之后后續(xù)很多鏈表題都用它來生成測試數(shù)據(jù)省了在紙上畫圖的時(shí)間。5.2 從141到142找環(huán)的入口才是高頻進(jìn)階141 判斷是否有環(huán)之后142 題要求找到環(huán)的入口節(jié)點(diǎn)。它的解法建立在快慢指針相遇點(diǎn)的基礎(chǔ)上設(shè)鏈表頭到環(huán)入口的距離為a環(huán)入口到相遇點(diǎn)的距離為b環(huán)剩余長度為c。slow走了abfast走了abk(abc)因?yàn)閒ast速度是slow的兩倍于是可以推出a c (k-1)(bc)。這意味著如果此時(shí)讓一個(gè)指針從鏈表頭出發(fā)另一個(gè)從相遇點(diǎn)出發(fā)都一次走一步它們必然在環(huán)入口相遇。這個(gè)推導(dǎo)看起來很數(shù)學(xué)但代碼和141幾乎一樣只在相遇后多了一段找入口的邏輯。如果141能理解142就是直接送分題。5.3 快慢指針?biāo)枷朐跀?shù)組類問題中的應(yīng)用不知道你有沒有發(fā)現(xiàn)題目熱詞里出現(xiàn)了數(shù)組尋找重復(fù)數(shù)之類的話題。287題尋找重復(fù)數(shù)用到的是一個(gè)非常巧妙的變形把數(shù)組下標(biāo)當(dāng)作鏈表節(jié)點(diǎn)索引數(shù)組值當(dāng)作next指針于是存在重復(fù)數(shù)就等價(jià)于鏈表有環(huán)。這類題做得多了會發(fā)現(xiàn)快慢指針不只是鏈表的專屬工具。只要能把數(shù)據(jù)關(guān)系抽象成從一個(gè)狀態(tài)跳轉(zhuǎn)到下一個(gè)狀態(tài)的圖且每個(gè)節(jié)點(diǎn)出度是 1判環(huán)問題就是快慢指針的菜。數(shù)組下標(biāo)跳轉(zhuǎn)、函數(shù)迭代、狀態(tài)機(jī)統(tǒng)統(tǒng)適用。5.4 面試加分項(xiàng)從一次筆試聊到工業(yè)實(shí)踐在我參與的面試?yán)锬艽鸪隹炻羔樀暮蜻x人不少但能主動說出哈希表適合需要記錄訪問歷史的場景快慢指針適合純判環(huán)場景的人少之又少。這其實(shí)就是考察你有沒有在真實(shí)項(xiàng)目里思考過數(shù)據(jù)結(jié)構(gòu)的取舍。比如說我們在做服務(wù)的分布式鏈路追蹤時(shí)遇到過調(diào)用鏈配置成環(huán)導(dǎo)致消息死循環(huán)的問題。那本質(zhì)和環(huán)形鏈表一模一樣每個(gè)節(jié)點(diǎn)指向下一個(gè)處理節(jié)點(diǎn)其中某個(gè)節(jié)點(diǎn)指向了前面某個(gè)節(jié)點(diǎn)消息就永遠(yuǎn)無法終止。當(dāng)時(shí)我們就是借鑒了快慢指針的思想在配置更新后做一次是否存在環(huán)的校驗(yàn)而不是等到線上循環(huán)打爆日志再去排查。這就是 LeetCode 141 的價(jià)值——它看起來只考一個(gè)鏈表實(shí)際上是一類有限狀態(tài)檢測循環(huán)的問題的通用解法。6. 刷題路線與實(shí)戰(zhàn)建議怎樣才算真正掌握這道題6.1 推薦進(jìn)階序列如果你剛做完 141我建議按這個(gè)順序往下刷142 環(huán)形鏈表 II找環(huán)入口練快慢指針的推導(dǎo)能力287 尋找重復(fù)數(shù)數(shù)組場景的快慢指針應(yīng)用感受抽象成鏈表的思維202 快樂數(shù)判斷是否進(jìn)入循環(huán)同樣是快慢指針的變體876 鏈表的中間結(jié)點(diǎn)快慢指針的另一類應(yīng)用快指針到終點(diǎn)慢指針剛好在中點(diǎn)。這幾題做完快慢指針的三大經(jīng)典考點(diǎn)判環(huán)、找環(huán)入口、找中點(diǎn)你就全覆蓋了。以后再碰到檢測循環(huán)的問題基本不用怕。6.2 常見錯誤清單我把自己刷題時(shí)踩過的坑匯總?cè)缦峦伺锌誻hile (fast ! null)里少了fast.next ! null導(dǎo)致空指針初始指針設(shè)置錯slow和fast都從head出發(fā)但沒有先排除head.next null的情況用節(jié)點(diǎn)值存哈希值和引用混淆重復(fù)值的用例直接誤判數(shù)組解法用了val作為標(biāo)記改壞原始數(shù)據(jù)后面想再遍歷鏈表時(shí)會出錯快慢指針相遇后沒有做任何后續(xù)處理就直接return true這個(gè)對 141 是對的但如果你直接改 142 就容易卡住。6.3 復(fù)盤模板每道鏈表題都該問自己三個(gè)問題刷題不能只追求 AC。每做完一道鏈表題我會強(qiáng)迫自己回答三個(gè)問題這道題除了我用的解法還有哪些解法它們的時(shí)空復(fù)雜度分別是什么如果鏈表是雙向的解法會變嗎如果允許改變鏈表結(jié)構(gòu)解法會變嗎這個(gè)解法能抽象成什么通用模式還能用在哪些看似不相關(guān)的題目上141 的答案分別是哈希表/數(shù)組/快慢指針雙向鏈表更容易判環(huán)可以直接查前驅(qū)標(biāo)記法會變簡單但會上報(bào)數(shù)據(jù)抽象出的通用模式是單步跳轉(zhuǎn)圖上的循環(huán)檢測。刷題數(shù)量多不多其實(shí)天花板很明顯。把每一道題像這樣反復(fù)拷打等到面試時(shí)哪怕遇到?jīng)]見過的新題也能很快把它歸到熟悉的問題模型里。以上算是我刷鏈表專題的一部分積累。環(huán)形鏈表只是一個(gè)起點(diǎn)快慢指針這個(gè)武器拿穩(wěn)了后面很多題都會輕松許多建議你親自畫一畫鏈表圖把相遇過程模擬兩遍勝過背十遍代碼。