环形链表 · 只判断有没有环(Floyd 快慢指针)

返回 true / false · 不找入口

给你一个链表 head,判断是否存在环。只返回 true 或 false,不需要环入口、不需要环长。找入口是 LC142 的内容;相遇点也不一定是环入口。

当前案例

values = [3, 2, 0, -4]

pos = 1 · index 3 的 next → index 1

hasCycle 返回

true

链表 · Floyd时间 O(n)空间 O(1)

两个案例 · 切换后整段讲解与动画重算

当前案例预期输出: true

七段讲解结构

① 题目

② 什么叫环

③ HashSet

④ 快慢指针

⑤ 逐步执行

⑥ Go 代码

⑦ 面试模板

LC141 vs LC142: LC141 只判有没有环;LC142 在判环之后还要找环入口。 slow 与 fast 的相遇点不一定是入口—— 例如 values=[3,2,0,-4], pos=1 时,相遇在 index 3,入口在 index 1。

1/12 · ① 题目 · 区块 1 · 题目到底问什么

讲解

给你一个链表 head,判断它里面是否存在环。只返回 true 或 false。不需要返回环入口,不需要返回环长度。LC141 是「判断有没有环」,不是「找到环入口」——找入口是 LC142。

LC141 ≠ LC142: 相遇点不一定是环入口

返回值只有布尔值;面试官若问入口,应切换到 LC142 的二次相遇推导。

输出 ∈ {true, false},与环长、相遇点坐标无关。

逐步执行表

step	slow	fast	说明
0	index 0	index 0	slow 与 fast 都从 head(index 0) 出发
1	index 1	index 2	slow 走一步,fast 走两步
2	index 2	index 1	fast 已经在环里绕回来了
3	index 3	index 3	slow 与 fast 在环内相遇,说明链表存在环 → return true

环入口 index 1 · 相遇点见高亮行 · LC141 不要求返回入口

Go 代码 · 同步高亮

1func hasCycle(head *ListNode) bool {
2    slow, fast := head, head
3 
4    for fast != nil && fast.Next != nil {
5        slow = slow.Next
6        fast = fast.Next.Next
7 
8        if slow == fast {
9            return true
10        }
11    }
12 
13    return false
14}

1. slow、fast 都从 head 出发
2. slow 每次一步,fast 每次两步
3. slow == fast → 环内相遇,return true
4. fast 或 fast.Next 为 nil → 无环,return false
5. 循环条件 fast != nil && fast.Next != nil 防空指针

核心结论

有环 → slow/fast 一定在环内相遇
无环 → fast 一定先到 nil
这题只判环,不找入口。

步骤时间线 · 12 帧

QA · 边界用例

场景	输入	期望	说明
head == nil	head = nil	false	循环不进入,直接 false
单节点无环	head = [1], pos = -1	false	fast 无法走两步,guard 失败 → false
单节点自环	head = [1], pos = 0	true	走一步后 slow==fast
有环主样例	values=[3,2,0,-4], pos=1	true	index 3 相遇,入口 index 1(不要求返回)
无环主样例	values=[1,2,3,4], pos=-1	false	fast 先到 nil