Floyd's Cycle Detection (龜兔賽跑演算法)

預備知識

Floyd's Cycle Detection（又稱龜兔賽跑演算法，Tortoise and Hare Algorithm）是 Two Pointers 「同向雙指標」手法的經典應用，專門用來判斷一個 Linked List（或任何「每個節點只指向下一個節點」的結構）是否存在環，並且能進一步找出環的起點。

白話理解

想像烏龜和兔子在同一個跑道上，同時從起點出發，烏龜（slow）一次走一步，兔子（fast）一次走兩步。

如果跑道是一直線（沒有環），兔子會先衝到終點，兩人永遠不會再相遇。
如果跑道是一個圈（有環），兔子跑得比較快，遲早會從後面「套圈」追上烏龜，兩人一定會在某一點相遇。

只要確認「兩人會不會相遇」，就能判斷跑道（Linked List）裡到底有沒有環，而且完全不需要額外的紙筆（額外的儲存空間）來記錄走過的路。

為什麼不直接用 Hash Set 記錄走過的節點？

判斷 Linked List 是否有環，最直覺的做法是用一個 Hash Table（或 Set）記錄「走過的每個節點」，如果走到一個已經記錄過的節點，就代表有環：

Python
JavaScript
Java

def has_cycle_with_set(head):
    visited = set()
    node = head
    while node:
        if node in visited:  # 這個節點來過了，代表有環
            return True
        visited.add(node)
        node = node.next
    return False

function hasCycleWithSet(head) {
  const visited = new Set();
  let node = head;
  while (node) {
    if (visited.has(node)) return true; // 這個節點來過了，代表有環
    visited.add(node);
    node = node.next;
  }
  return false;
}

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean hasCycleWithSet(ListNode head) {
        Set<ListNode> visited = new HashSet<>();
        ListNode node = head;
        while (node != null) {
            if (visited.contains(node)) return true; // 這個節點來過了，代表有環
            visited.add(node);
            node = node.next;
        }
        return false;
    }
}

這個做法時間複雜度是 O(n)，但空間複雜度也是 O(n)，因為最壞情況下要把整個 Linked List 的節點都記錄下來。

Floyd's Cycle Detection 的優勢在於：只用兩個指標（兩個變數），空間複雜度可以壓到 O(1)，這就是它特別的原因。

第一階段：判斷是否有環

Python
JavaScript
Java

def has_cycle(head):
    slow = head  # 龜：一次走一步
    fast = head  # 兔：一次走兩步

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:  # 兩者相遇，代表有環
            return True
    return False  # fast 先走到底（None），代表沒有環

function hasCycle(head) {
  let slow = head; // 龜：一次走一步
  let fast = head; // 兔：一次走兩步

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true; // 兩者相遇，代表有環
  }
  return false; // fast 先走到底（null），代表沒有環
}

class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head; // 龜：一次走一步
        ListNode fast = head; // 兔：一次走兩步

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true; // 兩者相遇，代表有環
        }
        return false; // fast 先走到底（null），代表沒有環
    }
}

第二階段：找出環的起點

常見誤解

很多人以為「兩個指標相遇的那個節點，就是環的起點」，其實不一定！相遇點通常只是環中間的某個位置，還需要多做一步才能找到真正的環起點。

找環起點的做法很巧妙：當兩個指標相遇後，把其中一個指標放回起點，兩個指標改成都「一次走一步」，再次相遇的地方，就是環的起點。

Python
JavaScript
Java

def detect_cycle_start(head):
    slow = head
    fast = head
    has_cycle = False

    # 第一階段：確認是否有環，並找到相遇點
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            has_cycle = True
            break

    if not has_cycle:
        return None  # 沒有環

    # 第二階段：一個指標回到起點，兩個指標都改成一次走一步
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next

    return slow  # 兩者再次相遇的節點，就是環的起點

function detectCycleStart(head) {
  let slow = head;
  let fast = head;

  // 第一階段：確認是否有環，並找到相遇點
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) break;
  }

  if (!fast || !fast.next) return null; // 沒有環

  // 第二階段：一個指標回到起點，兩個指標都改成一次走一步
  slow = head;
  while (slow !== fast) {
    slow = slow.next;
    fast = fast.next;
  }

  return slow; // 兩者再次相遇的節點，就是環的起點
}

class Solution {
    public ListNode detectCycleStart(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        boolean hasCycle = false;

        // 第一階段：確認是否有環，並找到相遇點
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }

        if (!hasCycle) return null; // 沒有環

        // 第二階段：一個指標回到起點，兩個指標都改成一次走一步
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow; // 兩者再次相遇的節點，就是環的起點
    }
}

逐步拆解：以 `A → B → C → D → E → (回到 C)` 為例

這個 Linked List 中，A、B 是進入環之前的節點，C 是環的起點，環的內容是 C → D → E → C。

第一階段：尋找相遇點

時刻	slow（一次一步）	fast（一次兩步）
起始	A	A
第 1 步	B	C（A → B → C）
第 2 步	C	E（C → D → E）
第 3 步	D	D（E → C → D）

兩者在 D 相遇，但 D 並不是環的起點（環的起點其實是 C）。

第二階段：找出真正的起點

把 slow 放回起點 A，fast 留在相遇點 D，兩者都改成一次走一步：

時刻	slow	fast
起始	A	D
第 1 步	B	E（D → E）
第 2 步	C	C（E → C）

兩者在 C 相遇，這正是環的起點！

為什麼這樣做就能找到起點？背後的數學

假設「起點到環起點」的距離是 a，「環起點到相遇點」的距離是 b，環的總長度是 L。

第一階段相遇時，可以證明 a 一定等於「相遇點沿著環再走 L - b 步」的距離（也就是 a ≡ L - b (mod L)）。這代表：從起點走 a 步會到環起點，和從相遇點沿環走 L - b 步也會到環起點，兩段路徑長度在數學上是等價的。所以只要讓一個指標從起點出發、另一個指標從相遇點出發，兩者都一次走一步，一定會同時抵達環的起點。

不需要死記這個推導，只要記得「相遇後其中一個指標歸零重新出發，兩個指標改成同速前進」這個操作口訣即可。

複雜度

方法	時間複雜度	空間複雜度
Hash Set 記錄走過的節點	O(n)	O(n)
Floyd's Cycle Detection	O(n)	O(1)

兩者時間複雜度相同，但 Floyd's Cycle Detection 完全不需要額外的資料結構，這也是它被稱為「空間複雜度最佳解」的原因。

適用情況

判斷 Linked List 是否有環：最經典的應用，例如 Leetcode: Linked List Cycle。
找出環的起點：例如 Leetcode: Linked List Cycle II。
找出 Linked List 的中點：fast 走到底時，slow 剛好停在中間，可參考 Leetcode: Middle of the Linked List。
在陣列上尋找重複的數字：如果把陣列的每個值都當成「指向下一個 index」的指標（nums[i] 代表下一步要跳到 index nums[i]），就能把問題轉換成 Linked List 的環偵測問題，例如 Leetcode: Find the Duplicate Number。
偵測任何「單一後繼者（Single Successor）」結構中的循環：只要一個結構滿足「每個節點都只指向下一個節點」，都可以套用這個技巧，不限於 Linked List。

常見誤區

誤以為相遇點就是環的起點：如上方警告所述，相遇點通常只是環中間的某個位置，一定要做完第二階段（其中一個指標歸零重新出發）才能找到真正的起點。
忘記同時檢查 fast 和 fast.next：如果只檢查 fast 是否存在，當 fast 剛好停在最後一個節點時，對 fast.next.next 取值會因為 fast.next 是 null 而出錯。
用來偵測「無向圖」或「有向圖」中的環：Floyd's Cycle Detection 只適用於「每個節點只有一個後繼者」的結構（Linked List、函數映射關係等）。一般 Graph 的環偵測，無向圖建議用 Union Find，有向圖則建議用 DFS 或參考 Topological Sort 的結果是否完整。
fast 和 slow 的移動速度設反或設成一樣：一定要讓 fast 走得比 slow 快（通常是 2 步 vs 1 步），如果兩者速度相同，就算真的有環，也永遠不會相遇。

為什麼不直接用 Hash Set 記錄走過的節點？​

第一階段：判斷是否有環​

第二階段：找出環的起點​

逐步拆解：以 A → B → C → D → E → (回到 C) 為例​

複雜度​

適用情況​

常見誤區​