环形链表 II

怎样从“链表 3→2→0→-4,-4.next 指回值为 2 的节点; 入口值 2,下标 1。”推导出 链表 · Floyd 两阶段，并证明每次状态变化都不会漏掉答案？

中心结论：第一阶段 slow/fast 找 meet; 第二阶段 p1 从 head、p2 从 meet 同速走,第二次相遇即 entry。

判断链表是否有环，不能使用额外的空间。如果有环，输出环的起点指针，如果没有环，则输出空。

在本站主例中，链表 3→2→0→-4,-4.next 指回值为 2 的节点; 入口值 2,下标 1。

算法最终需要得到或观察：返回值为 2 的节点(环入口),不是第一次相遇点。

复制整条链表或反复寻找前驱会重复走节点；哨兵和指针重连直接维护局部关系。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“链表指针接力”，明确答案需要观察什么。
2. 2状态只维护 meet、entry、p1、p2、距离 a/b/c。
3. 3转移每一步按照 第一阶段 slow/fast 找 meet; 第二阶段 p1 从 head、p2 从 meet 同速走,第二次相遇即 entry。
4. 4收尾读取 返回值为 2 的节点(环入口),不是第一次相遇点。，并复核边界与复杂度。

画清每根 next 指针改变前后的归属，再写代码。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：meet、entry、p1、p2、距离 a/b/c。

这道题是第 141 题的加强版。在判断是否有环的基础上，还需要输出环的第一个点。

分析一下判断环的原理。fast 指针一次都 2 步，slow 指针一次走 1 步。令链表 head 到环的一个点需要 x1 步，从环的第一个点到相遇点需要 x2 步，从环中相遇点回到环的第一个点需要 x3 步。那么环的总长度是 x2 + x3 步。

fast 和 slow 会相遇，说明他们走的时间是相同的，可以知道他们走的路程有以下的关系：

```c fast 的 t = (x1 + x2 + x3 + x2) / 2 slow 的 t = (x1 + x2) / 1

x1 + x2 + x3 + x2 = 2 * (x1 + x2)

所以 x1 = x3 ```

所以 2 个指针相遇以后，如果 slow 继续往前走，fast 指针回到起点 head，两者都每次走一步，那么必定会在环的起点相遇，相遇以后输出这个点即是结果。

第一阶段 slow/fast 找 meet; 第二阶段 p1 从 head、p2 从 meet 同速走,第二次相遇即 entry。

执行过程中持续维护：meet、entry、p1、p2、距离 a/b/c。

正确性依赖以下不变量：第一次相遇点 meet 不一定是 entry。；第二阶段 p1 与 p2 必须同速,不能继续 fast 走两步。

面试时可以压缩为：Floyd 两阶段: 第一阶段找 meet; 第二阶段 p1=head、p2=meet 同速走,第二次相遇为 entry。O(n)/O(1)。

落到当前题，执行机制可以压缩为：第一阶段 slow/fast 找 meet; 第二阶段 p1 从 head、p2 从 meet 同速走,第二次相遇即 entry。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入链表 3→2→0→-4,-4.next 指回值为 2 的节点; 入口值 2,下标 1。 因为：第一阶段 slow/fast 找 meet; 第二阶段 p1 从 head、p2 从 meet 同速走,第二次相遇即 entry。
2. 2Floyd 快慢指针若有环,两指针必相遇。 因为：快指针在环内追赶慢指针。
3. 3快慢继续前进继续检测。 因为：无环则 fast 先到 null。
4. 4快慢继续前进继续检测。 因为：无环则 fast 先到 null。
5. 5快慢相遇,确认有环相遇后 slow 回到 head。 因为：相遇点距环口与 head 距环口相等。
6. 6环入口在下标 0找到环的第一个结点。 因为：Floyd 判环 + 找入口 O(n)。
7. 7预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
8. 8收尾与复杂度返回值为 2 的节点(环入口),不是第一次相遇点。 因为：时间 O(n) · 空间 O(1)。第一阶段 slow/fast 找 meet; 第二阶段 p1 从 head、p2 从 meet 同速走,第二次相遇即 entry。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// ListNode define
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return nil
	}
	isCycle, slow := hasCycle(head)
	if !isCycle {
		return nil
	}
	fast := head
	for fast != slow {
		fast = fast.Next
		slow = slow.Next
	}
	return fast
}

func hasCycle(head *ListNode) (bool, *ListNode) {
	fast := head
	slow := head
	for slow != nil && fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
		if fast == slow {
			return true, slow
		}
	}
	return false, nil
}

func main() {
    // 1. 主例
    //    输入：mode="cycle", values=[3,2,0,-4], cycleAt=1
    //    期望：返回值为 2 的节点(环入口),不是第一次相遇点。
    //
    // 2. 失败 / 未命中
    //    检查：第一次相遇就 return slow(应 return entry)。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC141 环形链表；LC160 相交链表
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意链表 3→2→0→-4,-4.next 指回值为 2 的节点; 入口值 2,下标 1。
2. 2重复复制整条链表或反复寻找前驱会重复走节点；哨兵和指针重连直接维护局部关系。
3. 3优化第一阶段 slow/fast 找 meet; 第二阶段 p1 从 head、p2 从 meet 同速走,第二次相遇即 entry。
4. 4证明第一次相遇点 meet 不一定是 entry。；第二阶段 p1 与 p2 必须同速,不能继续 fast 走两步。
5. 5复杂度时间 O(n)，空间 O(1)