一、序
本文繼續給大家帶來一道和單鏈表相關的算法題。
之前聊到，如何對單鏈表是否存在環進行檢測，今天再來聊聊這個問題的進階的題：
- 一個單鏈表，如果有環，求環的入口。
- 一個單鏈表，如果有環，求環的長度。
鏈表這種結構，可以通過「指針」，將一組零散的內存塊串聯起來。那單鏈表，如果有環是一個什麼情況？
如上圖所示，單鏈表中如果存在環，一定有且只有一個入口點，進去了就別想出來，接下來我們看看如何找到這個環的入口。
二、檢測單鏈表環的入口
2.1 哈希法
哈希法的思路很簡單，如果單鏈表上有環，那必然有一個鏈表上靠後的結點的 next 指針，指向了一個靠前的結點。
那麼我們就可以通過一次循環加一個 Set 的輔助集合，來在每次循環的時候，判斷結點是否在 Set 中，如果沒有則將結點存入 Set 並繼續循環，有則找到了鏈表的入口。
<code>ListNodedetectCycle(ListNodehead){Set<listnode>visited=newHashSet<>();ListNodenode=head;while(node!=null){if(visited.contains(node))returnnode;visited.add(node);node=node.next;}}/<listnode>/<code>這種方式相對暴力，但是很好理解，只是需要額外消耗一個 Set 結構的空間，所以空間複雜度是 O(n)。同時它也是一種檢測單鏈表是否有環的解法。
2.2 雙指針法（Floyd算法）
在檢測單向鏈表是否有環的解法中，還有一個比較經典的雙指針來輔助計算，就是
快慢指針。解題思路就是使用 2 個指針，快指針每次走 2 步，慢指針每次走 1 步，如果鏈表有環，那麼它們肯定可以在環中相遇。就像兩個人在圓形的賽道上賽跑，一個跑的快另一個跑的慢，最終肯定是跑的快的人，追上了跑的慢的。
不過想用雙指針來確定單鏈表環的入口，思路上還有一些繞。
簡單來說，當快、慢兩個指針首次相遇後，再用兩個指針，指針 A 指向首次相遇的結點，指針 B 移動到單鏈表的頭結點，然後兩個指針分別每次向前移動 1 步，最終相遇的地方，就是單鏈表成環的入口。
先來說說思路，我們首先假設環足夠大，那麼在這道題裡，存在 3 個關鍵結點：鏈表頭結點、環入口結點、快慢指針首次相遇結點。通過這三個點可以將指針移動的路徑，分為 3 個區域。
從前面介紹的思路來說，當找到首次相遇點後，使用兩個指針，指針 A 指向首次相遇的點，指針 B 指向鏈表頭，兩個指針繼續同時向前走，每次走 1 步，最終會在鏈表環的入口處相遇。
既然 A、B 兩個指針，每次走 1 步，最終相遇的點，就是環的入口，那麼從步長來說 F = b，但是為什麼它們是相等的呢？Leetcode 給出一個 F = b 的指導公式，很清晰，我貼出來大家參考一下。
如果公式不好理解，我再用文字描述一下思路。為了簡化問題，我們只考慮環很大的情況（後面解釋），最少是 2 倍於表頭結點到環入口結點的距離。
1. 首先每次快指針走 2 步，慢指針走 1 步，假設慢指針走了 F 步走到了環的入口處，此時快指針走了 2F 步。
2. 當慢指針在環的入口點時，此時快指針距離入口點，已經走了 F 步了，多說一句 F 就是鏈表頭到環入口結點的距離。此時慢指針（slow） 和快指針（fast）都在環上，可將環分為 n（紅色）和 b（藍色） 兩個區域，此時 b == F。
3. 接下來快、慢指針繼續向前走，快指針想要追上慢指針，只有一種情況，就是慢指針走了 b 步，而快指針走了 2b 步，跨越了環入口結點。可以簡單理解這個圓環，以環入口點到圓心為軸，翻轉了一次。
到這裡應該就清晰了，剩餘的 b 區域，其實就等於 F 區域，所以再用兩個指針，分別在相遇結點和頭結點繼續向前走，每次走 1 步，最終兩個指針會在入環點相遇。
直接上代碼。
<code>publicListNodedetectCycle(ListNodehead){ListNodeslow=head,fast=head; while(true){if(fast==null||fast.next==null)returnnull; slow=slow.next;fast=fast.next.next; if(fast==slow)break;} fast=head;while(slow!=fast){slow=slow.next;fast=fast.next;}returnfast;}/<code>到這裡這個問題就說清楚了，不過我看不少人還有一些小疑問，這裡也一併解答。
前面說到，為了簡化問題，我們的前提條件是環很大，那麼在環很小的時候呢？
大與小本身就是一個相對的概念，在鏈表成環的場景下，說環很大的意思是在慢指針走到入環結點時，快指針還沒有走完一圈。也就是說，要滿足這個條件 2F < C，F 為鏈表頭結點到入環結點的長度，C 為環長度，這裡面有兩個變量。
這就清晰了，要麼真的是個很大的環，要麼 F 的長度很短，都可以說是「小環」，此時慢指針走到入環結點時，快指針已經在環內空轉了 n 圈了。
環小的情況，其實和環大的情況是一樣的，只是人為的覺得快指針多跑了很多圈，好像更復雜一些，這裡說兩個思考模型，來幫助我們思考。
1. 小環展開成大環。可以將小環循環鋪開，虛擬展開成一個大環去理解。
2. 從單鏈表上，去掉環內空轉的長度。我們其實不關心鏈表表頭到入環結點的實際距離，我們只是為了求入環點，所以可以直接將快指針在環內空轉的距離，從單鏈表上去掉。
這 2 個思考模型，都是為了幫助我們更好的理解和抽象問題，其實在「小環」的場景下，慢指針走到入環結點時，快指針已經在環內空轉了很多圈了，所以其實這並不影響我們計算的結果。
找到入環結點，那麼環的長度的算法，就是單鏈表求長度的算法，很簡單，這裡就不上代碼了。
三、小結時刻
本文聊到了單鏈表如果有環，如何找到環的入口。舉了兩個解決方案，分別是哈希法和雙指針法，雙指針的方式，理解起來有一些繞，不過按照本文的步驟，多思考一下應該就可以理解。
這道題也是 leetcode 上第 142 題，我也是看到不少人在評論裡，對官方的公式有疑問，所以才有了這篇文章。
算法沒什麼取巧的，多寫多練多思考才是正途。
今天就到這裡，本文對你有幫助嗎？留言、轉發、點收藏是最大的支持，謝謝！
在頭條號私信我。我會送你一些我整理的學習資料，包含：Android反編譯、算法、設計模式、虛擬機、Linux、Kotlin、Python、爬蟲、Web項目源碼。
閱讀更多 承香墨影 的文章
