13 KiB
tags, create time
| tags | create time | ||||||
|---|---|---|---|---|---|---|---|
|
2026-05-16 15:00 |
25-环形链表
题面
给你一个链表的头节点 head，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。**注意：pos 不作为参数进行传递。**仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true。否则，返回 false。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
提示：
- 链表中节点的数目范围是
[0, 10^4] -10^5 <= Node.val <= 10^5pos为-1或者链表中的一个有效索引
进阶：你能用 O(1)（即，常量）内存解决此问题吗？
思路
[!question] 💡 核心直觉 想象两个人在同一条跑道上赛跑——一个人跑得快，另一个人跑得慢。如果他们都在同一条封闭跑道上，快的迟早会从后面追上慢的。但如果是在直线跑道上，快的最终会冲到前面再也不回头。
把这个想法映射到链表上： 如果有环，快慢两个指针就会像跑道上的运动员一样"相遇"；如果没有环，快的会先走到终点
nil。
[!info] 🧩 两种基本思路
| 方法 | 时间复杂度 | 空间复杂度 | 能否满足进阶要求？ |
|---|---|---|---|
| 哈希集合记录已访问节点 | O(n) | O(n) | ❌ |
| 快慢指针（Floyd 判圈算法） | O(n) | O(1) | ✅ |
方法一：哈希集合（直觉方案）
维护一个已经遍历过的节点的集合。每到一个新节点就检查是否已经在集合中出现过：出现过说明有环；没出现过就加入集合并继续前进；走到 nil 说明无环。
flowchart TD
START(["从头节点出发"]) --> CHECK{"节点已在集合中?"}
CHECK -->|是| HASLOOP["🔄 发现环 → 返回 true"]
CHECK -->|否| ADD["加入集合"]
ADD --> NILCHECK{"节点是否为 nil?"}
NILCHECK -->|否| NEXT["移动到下一个节点"]
NEXT --> CHECK
NILCHECK -->|是| NOLOOP["✅ 走到末尾 → 返回 false"]
style HASLOOP fill:#f99,stroke:#333
style NOLOOP fill:#4c4,stroke:#333
步骤拆解：
| 步骤 | 动作 | 说明 |
|---|---|---|
| 1 | 初始化空哈希集合 | 存储已访问的节点引用（地址） |
| 2 | 遍历链表，对每个节点查集合 | 若存在则有环 |
| 3 | 不存在则加入集合，继续走 | 直到节点为 nil |
| 4 | 走到 nil 则无环 |
返回 false |
时间复杂度：O(n) — 每个节点最多访问一次，哈希集合的插入和查找都是 O(1)。
空间复杂度：O(n) — 最坏情况下需要存储所有 n 个节点的引用。
[!note] 🤔 这个方法的问题是什么？ 完全能正确检测环，但空间复杂度为 O(n)，不满足进阶的 O(1) 空间要求。而且它需要额外的数据结构开销。有没有可能只靠指针本身来完成检测？
方法二：快慢指针 / Floyd 判圈算法 ⭐（最优，O(1) 空间）⭐
[!warning] ⚠️ 核心类比 这是本道题的灵魂思想，建议反复体会：
- 直线跑道（无环）： 快指针每次走两步，慢指针每次走一步 → 快指针先到终点
nil- 环形跑道（有环）： 快指针进入环后绕圈，慢指针也在环里慢慢走 → 快指针从后面追上慢指针
算法原理
设定两个指针：slow 每次走一步，fast 每次走两步。让它们在链表中同时前进。
为什么一定能在环内相遇？
[!question] 💡 数学直觉 当两个指针都进入环之后，它们之间的距离变化是怎样的？
假设某一时刻两指针都在环内，相距 k 步（沿着移动方向计量）。每一步操作中：
- 慢指针向前走 1 步
- 快指针向前走 2 步
- 两者距离缩短 1 步
初始状态: S · · · · F （相距 k=4）
第1步后: S · · · F · （相距 k=3）
第2步后: S · · F · · （相距 k=2）
第3步后: S · F · · · （相距 k=1）
第4步后: S F · · · · （相遇！k=0）
因此，只要两指针都在环内，最多经过 k 步（k 为入环后的距离），快指针就能追上慢指针。
[!danger] ⛔ 常见误区澄清 快指针不会"跳过"慢指针！ 有人担心快指针一步跨过慢指针所在的位置而永远不会相等。但实际上在离散的一步移动中，快指针只能比慢指针多走 1 步，所以它会恰好落在慢指针所在的那个节点上，不可能跳过。
边界情况处理
flowchart LR
subgraph "空链表"
A1["head == nil"] --> R1["直接返回 false ✓"]
end
subgraph "单节点、无环"
A2["head.Next == nil"] --> R2["fast=head.Next=nil\n不进入循环\n返回 false ✓"]
end
subgraph "两节点、有环（连回自身）"
A3["1→2→1→..."] --> R3["一轮相遇!\nslow=2, fast=2 ✓"]
end
subgraph "普通有环"
A4["长链表+环"] --> R4["快追慢 → 环内某处相遇 ✓"]
end
style R1 fill:#4c4,stroke:#333
style R2 fill:#4c4,stroke:#333
style R3 fill:#4c4,stroke:#333
style R4 fill:#4c4,stroke:#333
关键细节： 循环条件为 fast != nil && fast.Next != nil，确保 fast.Next.Next 安全。
[!info] 🧮 为什么 fast 要检查 fast.Next != nil？ 因为
fast每次要走两步（fast = fast.Next.Next）。如果只检查fast != nil而不检查fast.Next != nil，当fast指向最后一个节点时，fast.Next为nil，fast.Next.Next就会 panic。
完整流程图解
以 3→2→0→-4→(回到索引1的节点2) 为例：
初始: slow=3(head), fast=3(head)
第1轮: slow→2, fast→0 （slow 走1步, fast 走2步）
第2轮: slow→0, fast→-4 （slow 走1步, fast 走2步）
第3轮: slow→-4, fast→2 （slow 走1步, fast 走2步, fast 进入环）
第4轮: slow→2, fast→2 （SLOW == FAST → 有环！✓）
flowchart TD
START(["head = 3→2→0→-4(连回索引1)"]) --> INIT["slow=3, fast=3"]
INIT --> LOOP{"fast!=nil && fast.Next!=nil"}
LOOP -->|是| STEP1["slow→下一步"]
STEP1 --> STEP2["fast→下两步"]
STEP2 --> MEET{"slow==fast?"}
MEET -->|是| HASLOOP["🔄 有环 → true ✓"]
MEET -->|否| LOOP
LOOP -->|否| NOLOOP["✅ 无环 → false ✗"]
style HASLOOP fill:#f99,stroke:#333
style NOLOOP fill:#4c4,stroke:#333
时间复杂度：O(n) — 如果存在环，慢指针最多走环外部分 + 一圈环内，快指针最多走环外部分 + 两圈环内。总步数不超过 2n。
空间复杂度：O(1) — 只用了 slow、fast 两个指针变量，完美满足进阶要求！
[!success] 🎯 Floyd 判圈算法的历史 这个算法由美国科学家 Robert W. Floyd 于 1967 年提出，是图论中经典的环路检测方法。它的精妙之处在于不需要任何额外存储空间，仅通过指针的速度差来探测拓扑结构，被誉为计算机科学中最优雅的算法之一。
代码提示
伪代码模板
// ① 边界检查：空链表直接无环
if head == nil {
return false
}
// ② 初始化双指针
slow := head // 每次走一步
fast := head // 每次走两步
// ③ 同步推进 —— 快指针能走两步时才继续
for fast != nil && fast.Next != nil {
slow = slow.Next // 慢指针前进一步
fast = fast.Next.Next // 快指针前进两步
if slow == fast { // 在环内相遇了！
return true
}
}
// ④ 快指针触底，无路可走 → 无环
return false
Go 语言技巧：
- Go 支持匿名多赋值，可以用一行完成两个指针的移动，但分写更清晰易读
- 利用 Go 的
&&短路特性：fast != nil && fast.Next != nil保证安全 - Go 的指针语义天然适合此算法——比较的是节点引用（地址），而非值
技巧
[!tip] 🔑 核心模式：Floyd 判圈算法（Tortoise and Hare） 双指针速度差法 —— 慢指针一步、快指针两步。这是检测链表中是否存在环的标准 O(1) 空间解法。
记忆口诀："一快一慢，有环必遇；快碰底线，无环无疑。"
[!tip] 🔑 延伸变体：如果有环，如何找到入口节点？ 这是一个非常有趣的扩展（对应 LeetCode 142. 环形链表 II）。证明如下：
设：
- x = 从 head 到环入口的距离
- y = 从环入口到相遇点的距离
- r = 环的周长
- L = 相遇时慢指针走过的总步数 = x + y
此时快指针走了 2L = x + y + n×r（n 为快指针在环内多走的圈数）。 化简得：x + y = n×r，即 x = n×r - y。
这意味着：从相遇点再走 (n-1) 圈 + 从 head 走 x 步，等于从环入口走 (n-1) 圈再走 y 步。
因此只需在第一次相遇后，把其中一个指针重新放回首部，两者各走一步，第二次相遇点就是环的入口节点。
// 第一次相遇后的入口查找 ptr1 := head ptr2 := slow // 或 fast，两者此刻相等 for ptr1 != ptr2 { ptr1 = ptr1.Next ptr2 = ptr2.Next } return ptr1 // 环的入口
[!note] 🐹 Go 中的链表定义 LeetCode 的 Go 环境内置如下结构体定义：
type ListNode struct {
Val int
Next *ListNode
}
不需要手动定义，直接在解题中使用即可。
[!info] 📊 两种方法对比
| 方法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 哈希集合 | O(n) | O(n) | 思路直观，容易想到 | 占用额外空间 |
| Floyd 判圈 ⭐ | O(n) | O(1) | 最优，面试标配 | 逻辑稍有门槛 |
[!success] ✅ 相关题目串联
- 26-环形链表 II — 进阶版：找环的入口（同一组快慢指针技术，加一步推导）
- 22-相交链表 — 同样是双指针的经典应用
- 24-回文链表 — 也用到了快慢指针找中点的技巧
[!warning] ⚠️ 面试注意事项
- Go 中不用显式释放资源，垃圾回收会自动处理，不需要也不应该手动置 nil 断链
- 快慢指针初始化都应该从
head开始，不要错误地把 fast 初始化为head.Next（那是回文链表的写法，不适用于本题）- 空链表
head == nil的情况需要考虑，虽然 LeetCode 测试用例通常不包含，但良好的习惯应该加上
代码
方法一：哈希集合（O(n) 空间）
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func hasCycle(head *ListNode) bool {
seen := make(map[*ListNode]bool)
for node := head; node != nil; node = node.Next {
if seen[node] {
return true // 该节点已出现过 → 有环
}
seen[node] = true
}
return false // 走到末尾也没重复 → 无环
}
方法二：Floyd 判圈算法 ⭐（最优 O(1) 空间）⭐
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func hasCycle(head *ListNode) bool {
// 空链表不可能有环
if head == nil {
return false
}
slow := head // 慢指针：每次走一步
fast := head // 快指针：每次走两步
// 快指针能连续走两步才继续推进
for fast != nil && fast.Next != nil {
slow = slow.Next // 慢指针前进一步
fast = fast.Next.Next // 快指针前进两步
if slow == fast { // 快慢指针相遇 → 有环
return true
}
}
// 快指针触底 → 无环
return false
}
[!tip] 🔑 精简写法（竞赛向） 利用 Go 的
for不带初始化语句的特性，可以让代码更紧凑：
func hasCycle(head *ListNode) bool {
for slow, fast := head, head; fast != nil && fast.Next != nil; {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
return true
}
}
return false
}
[!success] ✅ 运行验证 这是 LeetCode 第 141 题，通过率约 48%。看似简单的一道题，但其背后的 Floyd 判圈算法却是图论中一个经典而优雅的技巧——仅凭两个指针的速度差异就能判断整个图的拓扑结构。掌握这个模式，不仅能秒杀环形链表系列题目，也为后续学习图论中的环路检测打下基础。