好的，我们接下来讲解 LeetCode 第 142 题「环形链表 II」。

题目描述

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

说明：

• 不允许修改给定的链表。
• 如果链表中有环，请找出环的入口点。

示例：

输入：head = [3,2,0,-4], pos = 1 （pos 表示尾节点连接到的节点索引，仅用于表示环，不作为参数传入）
输出：返回索引为 1 的节点
解释：链表中有一个环，其尾部连接到第二个节点。

解题过程

步骤 1：判断链表是否有环（使用快慢指针）

首先，我们需要确定链表是否有环。一个经典的方法是使用 快慢指针（Floyd 判圈算法）：

• 慢指针 slow 每次走一步。
• 快指针 fast 每次走两步。

如果链表无环，fast 会先到达尾部（null），此时返回 null。
如果链表有环，fast 会进入环内绕圈，最终 slow 和 fast 会在环内的某一点相遇。

为什么一定会相遇？
因为 fast 相对于 slow 的速度是 1 步/次，所以在环内 fast 一定会追上 slow。

步骤 2：找到环的入口（数学推导）

假设相遇时：

• 从头节点到环入口的距离为 a（未知）。
• 环入口到相遇点的距离为 b。
• 相遇点再回到环入口的距离为 c（即环的长度 = b + c）。

相遇时：

• slow 走的距离：a + b。
• fast 走的距离：a + b + k*(b + c)，其中 k 是整数，表示 fast 在环内绕了 k 圈。

因为 fast 速度是 slow 的两倍，所以：

\[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，等于从相遇点走到环入口的距离 c，再加上 k-1 圈环的长度。

步骤 3：双指针二次相遇法

根据上面的推导，我们可以：

1. 当 slow 和 fast 在环内相遇时，将 fast 重新指向头节点。
2. 然后 slow 和 fast 同时每次走一步。
3. 它们再次相遇的节点就是环的入口。

为什么？

• fast 从头节点走 a 步到达环入口。
• slow 从相遇点走 c 步也到达环入口（因为 a = c + 整数圈，所以 slow 走 c 步时，fast 正好走 a 步，两者在环入口相遇）。

步骤 4：算法实现

def detectCycle(head):
    if not head or not head.next:
        return None
    
    slow = head
    fast = head
    
    # 第一步：判断是否有环
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # 无环
    
    # 第二步：寻找环入口
    fast = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    return slow

复杂度分析：

• 时间复杂度：O(n)，n 为链表节点数。
• 空间复杂度：O(1)，只用了两个指针。

总结

• 快慢指针 不仅可以判断环的存在，还能通过数学推导找到环的入口。
• 关键公式：a = c + (k-1)环长，从而得出二次相遇法。
• 这个方法高效且不需要额外空间，是解决此类问题的标准方案。