好的，我们这次来详细讲解 LeetCode 第 142 题：环形链表 II（Linked List Cycle II）。

1. 题目描述

给定一个链表的头节点 head，返回链表开始入环的第一个节点。
如果链表无环，则返回 null。

说明：

• 不允许修改给定的链表。
• 如果链表有环，链表的尾部节点的 next 指针会指向链表中的某个节点（而不是 null）。
• 要求时间复杂度 O(n)，空间复杂度 O(1)。

2. 题目理解与示例

示例 1（有环）：

3 → 2 → 0 → -4
     ↑        ↓
     ← ← ← ← ←

输入：head = [3,2,0,-4]，-4 的 next 指向 2。
输出：返回节点 2（值为 2 的节点），因为它是环的入口。

示例 2（有环）：

1 → 2
↑   ↓
← ← ←

输入：head = [1,2]，2 的 next 指向 1。
输出：返回节点 1。

示例 3（无环）：

1

输入：head = [1]
输出：null

3. 解题思路的循序渐进讲解

3.1 基础判断：链表是否有环？

我们先用 快慢指针法（Floyd 判圈法） 判断是否有环：

• 快指针 fast 每次走 2 步，慢指针 slow 每次走 1 步。
• 如果 fast 遇到 null（即链表尾部），说明无环，返回 null。
• 如果 fast == slow，说明有环。

为什么快慢指针一定会相遇？
因为如果有环，快指针会先进入环，慢指针后进入环。在环内，快指针相对于慢指针每次靠近 1 步，所以一定会相遇。

3.2 找到环的入口

这是本题的关键。假设：

• 链表头到环入口的长度（节点数）为 a。
• 环入口到快慢指针相遇点的长度为 b。
• 相遇点继续走到环入口的长度为 c。
• 环的长度为 b + c。

相遇时：

• 慢指针走了 a + b 步。
• 快指针走了 a + b + k(b + c) 步，其中 k 是快指针在环内转的圈数（k ≥ 1）。

因为快指针速度是慢指针的 2 倍，所以：

2(a + b) = a + b + k(b + c)

化简：

a + b = k(b + c)
a = k(b + c) - b
a = (k-1)(b + c) + c

关键结论：
a = (k-1)环长 + c，即 从头节点到环入口的距离 a，等于从相遇点走到环入口的距离 c 加上 k-1 圈环长。

3.3 如何利用这个结论找入口？

1. 当快慢指针在环内相遇时，把一个指针放回头节点 head。
2. 两个指针都每次走 1 步。
3. 它们再次相遇的节点就是环的入口。

为什么？

• 从 head 走 a 步到入口。
• 从相遇点走 c 步也到入口（因为 a = c + 整数倍环长，走 c 步刚好入口）。

4. 算法步骤

1. 初始化 slow = head, fast = head。
2. 循环：
   • 如果 fast 为 null 或 fast.next 为 null，返回 null（无环）。
   • slow = slow.next
   • fast = fast.next.next
   • 如果 slow == fast，跳出循环（有环）。
3. 将 fast 重新指向 head。
4. 当 fast != slow：
   • fast = fast.next
   • slow = slow.next
5. 返回 fast（或 slow，此时它们指向环入口）。

5. 代码实现（Java）

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        
        // 第一步：判断是否有环
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break;  // 相遇，有环
            }
        }
        
        // 无环情况
        if (fast == null || fast.next == null) {
            return null;
        }
        
        // 第二步：找环入口
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        
        return fast;
    }
}

6. 举例验证

示例 1：3 → 2 → 0 → -4，-4 指向 2。

• a=1（节点 3 到节点 2 距离 1）
• 环：2→0→-4→2，环长 3。
• 快慢指针在 -4 相遇（b=2，c=1）。
• 公式：a=1，c=1，a=c 成立（k=1 时）。
• 从头走 1 步到 2，从相遇点走 1 步也到 2，正确。

7. 复杂度分析

• 时间复杂度：O(n)，最多遍历两轮链表。
• 空间复杂度：O(1)，只用了两个指针。

这样一步步分析，你应该能完全理解 环形链表 II 的解法原理了。