LeetCode Linked List Cycle II：找環入口節點（Floyd 算法進階）

題目

給定單鏈表頭節點 head，判斷是否有環，若有則返回環的入口節點，否則返回 null。要求 O(n) 時間、O(1) 空間。

數學推導

設：

• 頭節點到環入口距離 = a
• 環長度 = c
• 入口到相遇點距離 = b
• 快指針走過 2s，慢指針走過 s

相遇時：2s = s + k*c → s = k*c。
慢指針走過 a + b = k*c → a = k*c - b。

意義：從頭節點走 a 步到入口；從相遇點繼續走 k*c - b 步（即繞環 k 圈再退 b）也到入口。
因此：一指針從 head，一指針從相遇點，同速前進，相遇點即入口。

算法步驟

1. 判斷有環：快慢指針，快每次 2 步，慢 1 步，相遇則有環。
2. 找入口：快指針重置為 head，雙指針同速（1 步）前進，相遇節點即入口。

Java 實現

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;

        ListNode slow = head.next;
        ListNode fast = head.next.next;

        // Phase 1: 找相遇點
        while (fast != null && slow != fast) {
            slow = slow.next;
            fast = (fast.next != null) ? fast.next.next : null;
        }
        if (fast == null) return null; // 無環

        // Phase 2: 找入口
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow; // 或 fast
    }
}

複雜度分析

• 時間：O(n)。Phase 1 至多 a + c 步，Phase 2 至多 a 步。
• 空間：O(1)，僅兩指針。

易錯點

• 快指針移動時需檢查 fast.next != null 再取 fast.next.next，否則 NPE。
• Phase 2 中 快指針重置為 head，而非保持在相遇點。
• 鏈表長度 1 或 2 時的邊界處理。

總結

本題是 Floyd 判環算法的經典延伸。核心洞見：a = k*c - b 使得「頭節點到入口」與「相遇點繞環到入口」距離相等。掌握此推導，可舉一反三解決「環長度」、「環入口前節點數」等變體。