387 lines
13 KiB
Markdown
387 lines
13 KiB
Markdown
---
|
||
tags: ["LeetCode", "链表", "双指针", "哈希表", "Floyd判圈", "简单"]
|
||
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^5`
|
||
- `pos` 为 `-1` 或者链表中的一个有效索引
|
||
|
||
**进阶：你能用 O(1)（即，常量）内存解决此问题吗？**
|
||
|
||
---
|
||
|
||
## 思路
|
||
|
||
> [!question] 💡 核心直觉
|
||
> 想象两个人在同一条跑道上赛跑——一个人跑得快，另一个人跑得慢。如果他们都在同一条**封闭跑道**上，快的迟早会从后面追上慢的。但如果是在**直线跑道**上，快的最终会冲到前面再也不回头。
|
||
>
|
||
> **把这个想法映射到链表上：** 如果有环，快慢两个指针就会像跑道上的运动员一样"相遇"；如果没有环，快的会先走到终点 `nil`。
|
||
|
||
> [!info] 🧩 两种基本思路
|
||
|
||
| 方法 | 时间复杂度 | 空间复杂度 | 能否满足进阶要求？ |
|
||
|------|-----------|-----------|-----------------|
|
||
| 哈希集合记录已访问节点 | O(n) | O(n) | ❌ |
|
||
| **快慢指针（Floyd 判圈算法）** | **O(n)** | **O(1)** | ✅ |
|
||
|
||
---
|
||
|
||
### 方法一：哈希集合（直觉方案）
|
||
|
||
维护一个已经遍历过的节点的集合。每到一个新节点就检查是否已经在集合中出现过：出现过说明有环；没出现过就加入集合并继续前进；走到 `nil` 说明无环。
|
||
|
||
```mermaid
|
||
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 步，所以它会恰好落在慢指针所在的那个节点上，不可能跳过。
|
||
|
||
#### 边界情况处理
|
||
|
||
```mermaid
|
||
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 → 有环！✓）
|
||
```
|
||
|
||
```mermaid
|
||
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 步。**
|
||
>
|
||
> 因此只需在第一次相遇后，把其中一个指针重新放回首部，两者各走一步，第二次相遇点就是**环的入口节点**。
|
||
>
|
||
> ```go
|
||
> // 第一次相遇后的入口查找
|
||
> ptr1 := head
|
||
> ptr2 := slow // 或 fast，两者此刻相等
|
||
> for ptr1 != ptr2 {
|
||
> ptr1 = ptr1.Next
|
||
> ptr2 = ptr2.Next
|
||
> }
|
||
> return ptr1 // 环的入口
|
||
> ```
|
||
|
||
> [!note] 🐹 Go 中的链表定义
|
||
> LeetCode 的 Go 环境内置如下结构体定义：
|
||
|
||
```go
|
||
type ListNode struct {
|
||
Val int
|
||
Next *ListNode
|
||
}
|
||
```
|
||
|
||
不需要手动定义，直接在解题中使用即可。
|
||
|
||
> [!info] 📊 两种方法对比
|
||
|
||
| 方法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|
||
|------|-----------|-----------|------|------|
|
||
| 哈希集合 | O(n) | O(n) | 思路直观，容易想到 | 占用额外空间 |
|
||
| **Floyd 判圈 ⭐** | **O(n)** | **O(1)** | **最优，面试标配** | 逻辑稍有门槛 |
|
||
|
||
> [!success] ✅ 相关题目串联
|
||
> - [[26-环形链表 II]] — 进阶版：找环的入口（同一组快慢指针技术，加一步推导）
|
||
> - [22-相交链表](./22-相交链表.md) — 同样是双指针的经典应用
|
||
> - [24-回文链表](./24-回文链表.md) — 也用到了快慢指针找中点的技巧
|
||
|
||
> [!warning] ⚠️ 面试注意事项
|
||
> - Go 中不用显式释放资源，垃圾回收会自动处理，**不需要也不应该手动置 nil 断链**
|
||
> - 快慢指针初始化都应该从 `head` 开始，不要错误地把 fast 初始化为 `head.Next`（那是回文链表的写法，不适用于本题）
|
||
> - 空链表 `head == nil` 的情况需要考虑，虽然 LeetCode 测试用例通常不包含，但良好的习惯应该加上
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
### 方法一：哈希集合（O(n) 空间）
|
||
|
||
```go
|
||
/**
|
||
* 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) 空间）⭐
|
||
|
||
```go
|
||
/**
|
||
* 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` 不带初始化语句的特性，可以让代码更紧凑：
|
||
|
||
```go
|
||
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 判圈算法却是图论中一个经典而优雅的技巧——仅凭两个指针的速度差异就能判断整个图的拓扑结构。掌握这个模式，不仅能秒杀环形链表系列题目，也为后续学习图论中的环路检测打下基础。
|