环形链表 II · Floyd 两阶段找环入口

返回节点引用 · 不是 bool

给定链表 3 → 2 → 0 → -4，其中 -4.next 指回值为 2 的节点。返回环入口节点；无环返回 nil。

统一输入表达

链表：3 → 2 → 0 → -4
-4.next → 值为 2 的节点
入口：值为 2，下标 1

返回值

node(2)

Floyd 两阶段O(n) 时间O(1) 空间

LC141 vs LC142：LC141 只返回 true/false；LC142 要返回环入口节点。第一次相遇点记为 meet，环入口记为 entry，二者常常不是同一个节点。

案例切换

预期返回: node(value=2)

Step 1/9 · 题目与输入

当前发生了什么

给定链表：3 → 2 → 0 → -4，其中 -4.next 指回值为 2 的节点。目标不是判断有没有环，而是返回环开始的那个节点。入口：值为 2，下标 1。

LC141 判环 · LC142 找入口

机器状态：head = 3，entry = 2，下标 = 1

为什么正确：LC141 只需要判断是否有环；LC142 还要找到入口节点引用。

不变量：入口节点是环中第一个被重复进入的节点。

面试怎么说：这题用 Floyd 两阶段：先快慢指针相遇，再从 head 和 meet 同步走找入口。

常见误区

第一次相遇点 meet 不一定是环入口 entry,不能直接 return slow。
第二阶段两个指针必须同速各走一步,不能继续让 fast 走两步。
循环判空必须是 fast != nil && fast.Next != nil,否则 fast.Next.Next 会空指针。
返回的是节点引用(指针),不是节点的值;面试要写 return p1 而不是 return p1.Val。
链表无环时返回 nil,不要返回 meet 或任意猜测的下标。

slow / p1 fast p2 entry / 回边 meet 第二次相遇

Go 代码 · 分阶段高亮

1func detectCycle(head *ListNode) *ListNode {
2    slow, fast := head, head
3 
4    // 第一阶段：寻找 meet ← 第一阶段
5    for fast != nil && fast.Next != nil {
6        slow = slow.Next
7        fast = fast.Next.Next
8 
9        if slow == fast {
10            // 第二阶段：寻找 entry ← 第二阶段
11            p1 := head
12            p2 := slow
13 
14            for p1 != p2 {
15                p1 = p1.Next
16                p2 = p2.Next
17            }
18 
19            return p1
20        }
21    }
22 
23    return nil
24}

第一阶段(行 4–10)：slow 一步、fast 两步，找 meet
第二阶段(行 11–19)：p1 从 head、p2 从 meet，同速找 entry
无环时走不到 if slow==fast，最终 return nil

本步要点