142. 环形链表II（Linked List Cycle II）

频次 ★★★★★ · 难度 🟡 · 高频：字节/腾讯

题目

判断链表是否有环，如果有，返回环的入口节点；没有环则返回 null。

示例：

输入: 3 -> 2 -> 0 -> -4 -> (指回 2)
输出: 环入口为节点 2

思路

Floyd 判圈 + 数学推导：设链表头到环入口距离为 a，环入口到相遇点距离为 b，相遇点到环入口（沿环走）距离为 c。

• 慢指针走过 a + b，快指针走过 a + b + n(b + c)（多绕了 n 圈）。
• 快指针速度是慢指针 2 倍：2(a + b) = a + b + n(b + c)，化简得 a = n(b + c) - b = (n-1)(b+c) + c。

也就是说：从链表头和相遇点同时出发、每次都走一步，二者会在环入口相遇（因为头到入口是 a，相遇点到入口沿环走也恰好是 a，模一圈长度）。

代码

public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            ListNode ptr = head;
            while (ptr != slow) {
                ptr = ptr.next;
                slow = slow.next;
            }
            return ptr;
        }
    }
    return null;
}

复杂度

• 时间：O(n)
• 空间：O(1)

边界条件

• 无环：while 循环走到 fast == null 自然退出，返回 null。
• 环的入口就是头节点（整个链表都是环）：a == 0，第二阶段 ptr 从 head 出发和 slow 立即相遇（在 0 步内），正确返回头节点。
• 环只有一个节点（自环）：相遇点就是环入口本身，第二阶段两个指针同步走相同步数后相遇。

变式

• 只需要判断是否有环、不需要找入口：见 141. 环形链表，是本题的简化版。
• 求环的长度：找到相遇点后，让一个指针固定不动，另一个指针继续走，直到再次回到固定指针的位置，走过的步数就是环长。

易错点

• 第二阶段两个指针都是每次走一步，不是让 fast 继续走两步——这是很多人会搞混的地方。
• 判断相遇要用引用相等 slow == fast（第一阶段）和 ptr == slow（第二阶段），不能用值比较。

面试追问

• 能不能推导一下”从头和相遇点同时出发会在入口相遇”这个结论？ 设头到入口距离 a，入口到相遇点距离 b，相遇点沿环回到入口距离 c：第一阶段相遇时慢指针走了 a+b，快指针走了 2(a+b)，又因为快指针比慢指针多走整数圈 n(b+c)，联立得 a = (n-1)(b+c) + c，也就是说从头走 a 步和从相遇点沿环走 c（模一圈）步会到达同一个点——正是环入口。
• 这道题能不能用 HashSet 做，思路上有什么权衡？ 可以，遍历时把每个访问过的节点存入 HashSet，第一个重复出现的节点就是环入口；比双指针法更直观好理解，但需要 O(n) 额外空间，Floyd 判圈法的优势正是把空间降到 O(1)，这也是面试官考察的核心点。

关联题

• 同套路：141. 环形链表I —— 先把判环写熟，本题只是相遇后多走一段
• 进阶：287. 寻找重复数 —— 把数组下标当 next 指针，数组版找环入口，想通它才算真正掌握本题
• 易混：160. 相交链表 —— 都推路程等式，但一个消环内偏移、一个消长度差