环形链表

怎样从“values=[3,2,0,-4], pos=1 — 判断链表是否存在环,只返回 true/false。”推导出 链表 · 快慢指针，并证明每次状态变化都不会漏掉答案？

中心结论：Floyd 快慢指针:slow 走一步、fast 走两步;环内相遇则有环,fast 先到 nil 则无环。

判断链表是否有环，不能使用额外的空间。

在本站主例中，values=[3,2,0,-4], pos=1 — 判断链表是否存在环,只返回 true/false。

算法最终需要得到或观察：有环样例在 index 3 相遇返回 true;无环样例 fast 到 nil 返回 false。

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

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

1. 1建模把输入翻译成“链表指针接力”，明确答案需要观察什么。
2. 2状态只维护 slow/fast 所在 index、步数、是否相遇(相遇点≠环入口)。
3. 3转移每一步按照 Floyd 快慢指针:slow 走一步、fast 走两步;环内相遇则有环,fast 先到 nil 则无环。
4. 4收尾读取 有环样例在 index 3 相遇返回 true;无环样例 fast 到 nil 返回 false。，并复核边界与复杂度。

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

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：slow/fast 所在 index、步数、是否相遇(相遇点≠环入口)。

给 2 个指针，一个指针是另外一个指针的下一个指针。快指针一次走 2 格，慢指针一次走 1 格。如果存在环，那么前一个指针一定会经过若干圈之后追上慢的指针。

Floyd 快慢指针:slow 走一步、fast 走两步;环内相遇则有环,fast 先到 nil 则无环。

执行过程中持续维护：slow/fast 所在 index、步数、是否相遇(相遇点≠环入口)。

正确性依赖以下不变量：若有环,快慢必相遇;若无环,fast 先到达 null。

面试时可以压缩为：Floyd 判环:slow 1 步 fast 2 步,环内相遇返回 true;无环 fast 先到 null 返回 false。O(n)/O(1)。相遇点不一定是入口。

落到当前题，执行机制可以压缩为：Floyd 快慢指针:slow 走一步、fast 走两步;环内相遇则有环,fast 先到 nil 则无环。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入values=[3,2,0,-4], pos=1 — 判断链表是否存在环,只返回 true/false。 因为：Floyd 快慢指针:slow 走一步、fast 走两步;环内相遇则有环,fast 先到 nil 则无环。
2. 2Floyd 快慢指针若有环,两指针必相遇。 因为：快指针在环内追赶慢指针。
3. 3快慢继续前进继续检测。 因为：无环则 fast 先到 null。
4. 4快慢继续前进继续检测。 因为：无环则 fast 先到 null。
5. 5快慢继续前进继续检测。 因为：无环则 fast 先到 null。
6. 6快慢相遇,确认有环相遇后 slow 回到 head。 因为：相遇点距环口与 head 距环口相等。
7. 7环入口在下标 0找到环的第一个结点。 因为：Floyd 判环 + 找入口 O(n)。
8. 8收尾与复杂度有环样例在 index 3 相遇返回 true;无环样例 fast 到 nil 返回 false。 因为：时间 O(n) · 空间 O(1)。Floyd 快慢指针:slow 走一步、fast 走两步;环内相遇则有环,fast 先到 nil 则无环。

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

// ListNode define
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

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

func main() {
    // 1. 主例
    //    输入：mode="cycle", values=[3,2,0,-4], cycleAt=1
    //    期望：有环样例在 index 3 相遇返回 true;无环样例 fast 到 nil 返回 false。
    //
    // 2. 失败 / 未命中
    //    检查：一上来就判 slow==fast 会误判;必须先移动再比较。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC142 环形链表 II；LC876 中间结点
}

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

1. 1题意values=[3,2,0,-4], pos=1 — 判断链表是否存在环,只返回 true/false。
2. 2重复复制整条链表或反复寻找前驱会重复走节点；哨兵和指针重连直接维护局部关系。
3. 3优化Floyd 快慢指针:slow 走一步、fast 走两步;环内相遇则有环,fast 先到 nil 则无环。
4. 4证明若有环,快慢必相遇;若无环,fast 先到达 null。
5. 5复杂度时间 O(n)，空间 O(1)