判斷單向鏈表是否有環及求環入口的演算法數學證明
讀者好：歡迎閱讀與指正，本篇文章未經作者本人授權，禁止任何形式的轉載，謝謝！
第一次在知乎編輯公式，可能有些地方有瑕疵，可以移步個人 blog 閱讀：blog 原文
概要
本篇文章，主要講解 title 中所描述演算法的原理及數學證明。需要注意的是，本篇中出現的代碼未必是完整代碼，可能只是一個關鍵代碼塊，且採用 C++ 編寫。
判斷鏈表是否有環
當單向鏈表中存在環的時候，遍歷此鏈表會發生無限循環，無法到達末尾（實際上並沒有末尾）的情況，所以在可能發生這種情況的時候，需要檢查鏈表中是否存在一個環。
演算法
演算法很簡單，設置兩個指針，分別為快指針（fast）和慢指針（slow），快指針每次向前走兩步，慢指針每次走一步。如果快指針指向了 NULL，那麼說明此鏈表中沒有壞，因為有環會發生無限循環，不可能走到末尾。而在有環的情況下，兩個指針會在環里繞圈，最終指向同一個地址，即兩個指針相遇，根據這個就可以終止遍歷代碼且證實鏈表有環。
附上關鍵代碼：
ListNode *slow = head->next; ListNode *fast = slow->next; while (fast && slow != fast) { slow = slow->next; fast = fast->next ? fast->next->next : NULL; } return fast ? true : false;
有環時兩個指針一定會相遇的數學證明
在做這道題的時候可能會有疑惑：為什麼在有環的時候兩個指針一定會相遇？這裡給出數學證明。
當 slow 指針一步步走到環的入口時（注意此時 fast 已經在環里了，因為它比 slow 要快），設：
- 鏈表頭指針 head 到鏈表環的入口處的距離為
- fast 指針距離環的入口的距離為
- fast 已經在環內走了
圈（向下取整）
- 假設 slow 再經過
步與 fast 相遇
- 環的周長為
- fast 和 slow 走過的總路程分別為
和
示意圖如下：
則當 slow 走到環入口時，可得知：
又因為 fast 每次走兩步，即比 slow 快一倍，所以若兩個指針相遇，則有：
減去 是為了減掉不在環內的長度從而求得相遇點相對於環入口的距離（按照指針前進方向算），由於等式兩邊的值實際上是相對於環入口的距離，所以有：
可以看到， 和
的總和等於環的周長的整數倍，這個等式是成立的。實際上我們也求出了
的值。結合圖和最終的等式，我們可以看到，對於任意
，都可以求出無數個
值，每個值都對應一個周長的整數倍，而對於每一個
值，最終相遇的位置都一樣，這也很好理解，當 slow 和 fast 相遇後，由於 2 倍速度的關係，當 slow 繼續走半圈的時候，fast 走了一圈回到了之前的相遇點，當 slow 再走半圈回到之前的相遇點， fast 又走了一圈再次回到之前的相遇點。
這就是對於在有環的單鏈表中快慢指針一定會相遇的數學證明。
求環的入口
在上一個問題之後，還有一個相關的問題，即如果此鏈表有環，求環的入口節點。直接想此演算法可能比較難解，所以這個問題可以嘗試著從數學上入手。
數學
設 (注意與上一個問題所表示的含義可能有不同) ：
為鏈表頭 head 到環入口的距離
為從環入口向前到相遇點的距離 (按照指針前進的方向計算)
為從相遇點向前到環入口的距離 (按照指針前進的方向計算)
為環的周長
分別為 slow 和 fast 在相遇時走過的圈數（向下取整）
和
示意圖如下：
則：
又因為 fast 速度是 slow 的 2 倍，所以：
因為 fast 的速度是 slow 的兩倍，所以 至少是
的兩倍（至少而不是恰好是因為 fast 進入環時 slow 可能還沒進入環，所以 fast 可能會先在環內走幾圈），
即
這裡其實還可以求出的是，當 等於 2 倍的
的時候，
和
都為 0 ，也就是整個鏈表就是一個環 。
由此可以看出， 即鏈表頭 head 到環入口的距離就等於
，其實就等於
（注意
是按照指針前進方向算的，並不是最小距離，所以這個結果對於整個鏈表都是環也是有效的） ，而從相遇點向前走
的距離，正好就走到了環的入口（如果沒理解可以在圖上比劃一下即可），所以我們就可以推導出演算法，即：讓兩個指針其中一個從鏈表頭 head 出發，一次走一步，讓另一個指針從相遇點出發，也一次走一步，相遇點就是環的入口。
演算法
關鍵代碼如下：
slow = head; while (slow != fast) { slow = slow->next; fast = fast->next; }
注意事項
這裡有一個小坑，在演算法的最最開始，可以讓 slow 和 fast 都為 head 指針，或者 slow 為 head 的下一個節點，fast 為下兩個節點。如果讓 slow 為 head 指針，fast 為下一個節點，則可能無法求出環的入口，甚至可能陷入死循環。但對於第一個問題，這個步驟沒有影響。
推薦閱讀：