142. 环形链表 II#

问题升级：不止要找环，还要找入环点#

在上一题中，我们讨论了如何判断链表是否有环。现在让我们更进一步：如果确定链表中有环，我们该如何找到环的入口节点？这就像是在环形跑道上不仅要确认跑道是环形的，还要找到环形跑道的起点。

问题描述#

题目目标#

LeetCode第142题”环形链表 II”要求：给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

示例 1#

输入：

3 → 2 → 0 → -4
         ↑___________|

text

输出： 返回节点 2 链表示意：

3 -> 2 -> 0 -> -4
         ^___________|

text

说明： 链表中存在一个环，其尾部连接到第二个节点

补充说明#

链表题的输入本质上是节点之间的连接关系，重点通常是返回处理后的头节点或目标节点。

从快慢指针相遇谈起#

还记得上一题中的快慢指针相遇吗？那个相遇点看似随机，实际上蕴含着重要的数学原理。让我们用这个相遇点来找到入环点。

巧妙的数学关系#

假设：

链表头到入环点的距离为 a
入环点到相遇点的距离为 b
相遇点到入环点的距离为 c

当快慢指针相遇时：

慢指针走过的距离：a + b
快指针走过的距离：a + b + n(b + c)，其中n是快指针在环内走的圈数
因为快指针速度是慢指针的两倍，所以：2(a + b) = a + b + n(b + c)

通过解这个等式，我们发现：a = c + (n-1)(b + c) 这意味着：从链表头和相遇点同时出发，最终会在入环点相遇！

代码实现#

public ListNode detectCycle(ListNode head) {
    // 边界处理：空链表或单节点无后继，必然无环
    if (head == null || head.next == null) {
        return null;
    }

    // 第一阶段：使用快慢指针寻找“环内相遇点”
    // slow 每次1步，fast 每次2步
    ListNode slow = head;
    ListNode fast = head;
    // intersection：记录相遇节点；若始终为 null 说明无环
    ListNode intersection = null;

    while (fast != null && fast.next != null) {
        // 慢指针移动1步
        slow = slow.next;
        // 快指针移动2步
        fast = fast.next.next;
        // 相遇则说明存在环，保存相遇点并退出
        if (slow == fast) {
            intersection = slow;
            break;
        }
    }

    // 第一阶段未找到相遇点，直接返回 null（无环）
    if (intersection == null) {
        return null;
    }

    // 第二阶段：一个指针从头结点出发，另一个从相遇点出发
    // 二者同步每次走1步，再次相遇处就是入环点
    ListNode start = head;
    while (start != intersection) {
        start = start.next;
        intersection = intersection.next;
    }

    // 返回环的入口节点
    return start;
}

java

图解过程#

1) 初始状态：
3 → 2 → 0 → 4
    ↑___________|
S,F

2) 快慢指针相遇：
3 → 2 → 0 → 4
    ↑___________|
        S,F

3) 从头和相遇点同时出发：
3 → 2 → 0 → 4
    ↑___________|
P1      P2

4) 在入环点相遇：
3 → 2 → 0 → 4
    ↑___________|
    P1,P2

plaintext

与上一题的联系与进阶#

相比环形链表I，这一题是一个很自然的进阶：

两题都使用了快慢指针技巧
这一题复用了上一题找相遇点的过程
在找到相遇点后，增加了寻找入环点的步骤

实现细节与优化#

空间复杂度仍然保持O(1)
时间复杂度为O(n)
不需要额外的数据结构
代码实现优雅且直观

思考与延伸#

这个问题告诉我们：

有时问题的解决方案就藏在问题本身的特性中
数学关系可以帮助我们找到优雅的解法
快慢指针不仅能检测环，还能帮我们找到关键节点

实际应用思考#

这个算法的思想可以应用在很多实际场景中：

检测循环依赖
死锁检测
循环引用的处理

让我们记住：当我们遇到类似的”寻找特殊点”问题时，可以尝试利用路径特性来找到优雅的解决方案。