環形鏈表入口檢測算法數學解釋

數學原理

1. 假設定義:

   • 鏈表頭到環入口的距離為 a
   • 環入口到相遇點的距離為 b
   • 相遇點到環入口的距離為 c
   • 環的長度為 b + c

2. 第一次相遇時:

   • 慢指針走了 s = a + b 步
   • 快指針走了 f = a + b + n(b + c) 步，其中 n 是快指針在環內轉的圈數
   • 由于快指針速度是慢指針的2倍，所以 f = 2s

3. 代入求解:

   2(a + b) = a + b + n(b + c)
   a + b = n(b + c)
   a = n(b + c) - b
   a = (n-1)(b + c) + c
   

4. 關鍵結論:

   • 當 n=1 時，a = c
   • 這意味著：從鏈表頭到環入口的距離 = 從相遇點繼續走到環入口的距離

當n不等于1時

您提出了一個很好的問題！我們確實不知道具體的 n 值（快指針繞環的圈數）。讓我更清晰地解釋：當入口節點很遠，可能快指針早就到達環而且轉了好幾圈了

為什么 n 的具體值不重要

1. 我們證明了：a = (n-1)(b+c) + c，其中 a 是頭到環入口的距離，b+c 是環的周長。

2. 關鍵點：無論 n 是多少（1, 2, 3…），等式右邊 (n-1)(b+c) + c 都表示：

   • 先在環上走 n-1 個完整的圈（即 (n-1)(b+c)）
   • 再從相遇點繼續走 c 步

3. 這意味著：從相遇點走 c 步（可能再加上若干個環的周長）一定會到達環入口。

4. 同樣，從鏈表頭走 a 步也會到達環入口。

5. 由于 a = (n-1)(b+c) + c，如果同時：

   • 從鏈表頭開始走
   • 從相遇點開始走
   • 都用相同的速度（每次走1步）

   那么這兩個指針會同時到達環入口！

6. 一個放到頭節點走到入口節點 另一個從相遇點走到入口節點在轉了幾個整圈

實際上 n 的值怎么確定

在實際的鏈表環檢測中，n 值由快慢指針首次相遇時決定，但我們不需要計算它：

• 在標準鏈表（環不會特別大）中，通常 n=1。
• 即使 n>1，算法也能正確工作：
  • 快指針在相遇時可能多走了幾圈
  • 但在第二階段，從相遇點出發的指針會沿著相同的路徑（可能走幾圈）最終到達入口