確定鏈表中是否存在循環的算法

Question

所以我最近遇到了算法來確定一個循環是否存在於鏈表中。代碼如下：

public boolean hasCycle(ListNode head) { 
    if (head == null) { 
     return false; 
    } 
    ListNode fast = head; 
    ListNode slow = head; 
    while (fast != null) { 
     if (fast.next == null) { 
      return false; 
     } 
     if (fast.next == slow) { 
      return true; 
     } 
     fast = fast.next.next; 
     slow = slow.next; 
    } 
    return false; 
} 

當試圖證明該算法的正確性，我想出了一個主意： 假設週期的周長是「一」，前兩個指針相遇是過去的時間「T」。由於「快」節點的速度移動快兩倍的「慢」的節點，我們可以得到的數學關係：

2噸模A = t模一

現在，「一」是一個常量代表周長和「t」可能是1,2,3 ......那麼，我如何證明不管「a」的值是多少，我們總能找到一個「t」，這樣上面的等式是可解的？

Answer 1

您正處在正確的軌道上！提示：在a迭代之後，公式會發生什麼？

Answer 2

假設兩個指針開始於相同點處的週期內（這不能算作會議）

2t = t (a)

=>2t - t = 0 (a)

=>t = 0 (a)

這意味着在t = a * k，在經過時間是循環長度的倍數之後，兩個指針將在開始點相遇。

它是適用於所有a >= 2，因爲當時間等於所有k>1，慢指針正好運行k個圈長，而快速指針運行快兩倍，所以它運行2K週期長，他們仍然在滿足同一點是哪個起點。