142. 环形链表 II

我们可以使用 Floyd 判圈算法（快慢指针） 来高效解决。

🧠 思路解析

1. 判断是否有环：用快慢指针（slow 和 fast）。

   • slow 每次走 1 步，fast 每次走 2 步。
   • 如果有环，fast 最终会追上 slow（在环内某处相遇）。
   • 如果无环，fast 会走到 null。

2. 找到环的入口：

   • 假设链表头到环入口的距离为 a，
   • 环入口到相遇点的距离为 b，
   • 相遇点绕回环入口的距离为 c（即环长 = b + c）。
   • 当 slow 和 fast 相遇时：
     • slow 走了 a + b 步，
     • fast 走了 a + b + n(b + c) 步（n ≥ 1，表示 fast 在环里转了 n 圈）。
     • 又因为 fast 速度是 slow 的 2 倍 ⇒ 2(a + b) = a + b + n(b + c)
     • 化简得：a = n(b + c) - b = (n - 1)(b + c) + c
   • 所以：从 head 出发走 a 步，和从相遇点出发走 c 步（再绕若干圈），会同时到达环入口。

3. 操作：

   • 第一次相遇后，将一个指针放回头部，另一个留在相遇点。
   • 两个指针都每次走 1 步，再次相遇的位置就是环的入口。

✅ Java 实现

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

        ListNode slow = head;
        ListNode fast = head;

        // Step 1: 快慢指针找相遇点
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break; // 相遇
            }
        }

        // Step 2: 判断是否真的有环
        if (fast == null || fast.next == null) {
            return null; // 无环
        }

        // Step 3: 找环入口
        ListNode ptr1 = head;
        ListNode ptr2 = slow; // 或 fast，此时 slow == fast
        while (ptr1 != ptr2) {
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }

        return ptr1; // 环的入口
    }
}

⏱️ 时间 & 空间复杂度

• 时间复杂度：O(n)，每个节点最多访问常数次。
• 空间复杂度：O(1)，只用了几个指针。

💡 补充说明

• 如果题目只要求判断是否有环（LeetCode 141），只需第一步即可。
• 本题关键在于数学推导出 a = c + k * 环长，从而保证第二次同步走能命中入口。