441 lines
14 KiB
Markdown
441 lines
14 KiB
Markdown
---
|
||
tags: ["LeetCode", "链表", "双指针", "Floyd判圈", "环形链表"]
|
||
create time: 2026-05-16 15:30
|
||
---
|
||
|
||
# 26-环形链表 II
|
||
|
||
## 题面
|
||
|
||
给定一个链表的头节点 `head`，返回链表开始入环的第一个节点。**如果链表无环，则返回 `nil`。**
|
||
|
||
如果链表中有某个节点，可以通过连续跟踪 `next` 指针再次到达，则链表中存在环。
|
||
|
||
为了表示给定链表中的环，评测系统内部使用整数 `pos` 来表示链表尾连接到链表中的位置（索引从 0 开始）。**注意：pos 不作为参数进行传递。**仅仅是为了标识链表的实际情况。
|
||
|
||
**不允许修改链表。**
|
||
|
||
**示例 1：**
|
||
|
||
```
|
||
输入：head = [3,2,0,-4], pos = 1
|
||
输出：返回索引为 1 的链表节点
|
||
解释：链表中有一个环，其尾部连接到第二个节点。
|
||
```
|
||
|
||
**示例 2：**
|
||
|
||
```
|
||
输入：head = [1,2], pos = 0
|
||
输出：返回索引为 0 的链表节点
|
||
解释：链表中有一个环，其尾部连接到第一个节点。
|
||
```
|
||
|
||
**示例 3：**
|
||
|
||
```
|
||
输入：head = [1], pos = -1
|
||
输出：返回 null
|
||
解释：链表中没有环。
|
||
```
|
||
|
||
**提示：**
|
||
|
||
- 链表中节点的数目范围在 `[0, 10^4]` 内
|
||
- `-10^5 <= Node.val <= 10^5`
|
||
- `pos` 的值为 `-1` 或者链表中的一个有效索引
|
||
|
||
**进阶：你是否可以使用 O(1) 空间解决此题？**
|
||
|
||
---
|
||
|
||
## 思路
|
||
|
||
> [!question] 💡 承上启下
|
||
> 你已经掌握了 [25-环形链表](./25-环形链表.md)——用 Floyd 快慢指针判断环的存在性。现在问题是：**如果已经有环，如何找到入口节点？**
|
||
|
||
> [!tip] 🔑 结论先行
|
||
> 仍然使用快慢指针。第一次相遇后，把其中一个指针放回 `head`，两个指针改为**同速各走一步**，它们第二次相遇的位置就是环的入口。
|
||
> **时间复杂度 O(n)，空间复杂度 O(1)**。
|
||
|
||
### 前置回顾：第一轮——检测环
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
subgraph S ["慢指针 slow（每次 1 步）"]
|
||
S1["从头出发"]
|
||
end
|
||
subgraph F ["快指针 fast（每次 2 步）"]
|
||
F1["从头出发"]
|
||
end
|
||
|
||
S1 --> PULL{"两指针都进环后，快追慢"}
|
||
F1 --> PULL
|
||
PULL -->|每步缩小 1<br/>最多 r 步| MEET["🔄 环内相遇点 M"]
|
||
|
||
style MEET fill:#f99,stroke:#333
|
||
```
|
||
|
||
此时我们已经确认有环，但相遇点 M 通常**不是**入口 E。我们需要推导一个关系式来定位 E。
|
||
|
||
### 核心推导：第二轮——寻找入口
|
||
|
||
> [!question] 💡 设未知数
|
||
> 用三个变量描述链表的拓扑结构，你能建立它们之间的关系吗？
|
||
|
||
定义三个关键距离（沿链表前进方向计量）：
|
||
|
||
| 符号 | 含义 |
|
||
|------|------|
|
||
| **x** | 从 `head` 到环入口的距离（入口前非环部分的长度） |
|
||
| **y** | 从环入口到相遇点的距离 |
|
||
| **r** | 环的周长 |
|
||
|
||
**慢指针走过的总路程**（设为 L）：
|
||
|
||
$$L = x + y$$
|
||
|
||
> [!info] ℹ️ 为什么是 x + y？
|
||
> 慢指针速度为 1，先进入环，然后沿着环走到相遇点。它在进入环之后最多走不满一圈就遇到了快指针（因为快指针在后面追），所以路径就是"头→入口" + "入口→相遇点" = x + y。
|
||
|
||
**快指针走过的总路程**（设为 2L）：
|
||
|
||
$$2L = x + y + n \cdot r \quad (n \geq 1)$$
|
||
|
||
> [!info] 🧮 理解 n · r
|
||
> 快指针速度是慢指针的两倍，所以它除了走完和慢指针一样的 x + y 之外，还在环里多跑了若干整圈（n 圈）。由于快指针必须至少比慢指针多跑一圈才能追上它，所以 n ≥ 1。
|
||
|
||
将 L = x + y 代入消元：
|
||
|
||
$$2(x + y) = x + y + n \cdot r$$
|
||
|
||
化简得：
|
||
|
||
$$x + y = n \cdot r$$
|
||
|
||
移项得到关键公式：
|
||
|
||
$$\boxed{x = n \cdot r - y}$$
|
||
|
||
> [!warning] ⛔ 常见误区
|
||
> 这里 n 可以是 1、2、3……不一定等于 1。但无论如何，**这个等式的几何意义不变**：
|
||
|
||
### 公式解读：从两个方向走相同距离
|
||
|
||
$$x = n \cdot r - y = (n - 1) \cdot r + (r - y)$$
|
||
|
||
这意味着什么？让我们从两个视角看：
|
||
|
||
**视角 1 — 从 head 出发走 x 步**：直达环入口 E。
|
||
|
||
**视角 2 — 从相遇点 M 出发走同样的距离**：
|
||
|
||
```
|
||
M → E 的距离拆解:
|
||
先走完环的剩余部分 M→E：距离 = r - y
|
||
再绕 (n-1) 整圈回到 E：距离 = (n-1) · r
|
||
|
||
合计 = (n-1) · r + (r - y) = x ✅
|
||
```
|
||
|
||
> [!success] 🎯 关键洞察
|
||
> **从 head 走 x 步到达入口 E；从相遇点 M 也走 x 步同样到达入口 E。**
|
||
> 两者步数相同！所以我们只需要启动两个新指针——一个从 head 开始，一个从相遇点 M 开始——以相同速度同步前进，它们的第二次相遇点必然是环入口 E。
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
HEAD["head"] --"第1步"--> A["第1个节点"]
|
||
A --"第2步"--> B["第2个节点"]
|
||
B --"第x步"--> ENTRY["⭐ 环入口 E ← 两指针在此相遇"]
|
||
|
||
ENTRY -.-> RING["环中各节点..."]
|
||
RING -.-> ENTRY
|
||
|
||
MEET["相遇点 M"] --"走同样步数"--> ENTRY
|
||
|
||
style HEAD fill:#bbf,stroke:#333
|
||
style MEET fill:#fbf,stroke:#333
|
||
style ENTRY fill:#fd4,stroke:#333,stroke-width:3px
|
||
```
|
||
|
||
**示例完整演示**：以 `3→2→0→-4→(回索引1)` 为例
|
||
|
||
| 阶段 | 参数 | 值 |
|
||
|------|------|-----|
|
||
| 非环段 | x | 1（head 直接就是入口） |
|
||
| 环入口到相遇点 | y | 3（入口 2 → 0 → -4 → 2） |
|
||
| 环周长 | r | 4（2→0→-4→2） |
|
||
| 验证 | x + y = n × r | 1 + 3 = 4 = 1 × 4 ✓ |
|
||
| 入口公式 | x = n×r - y | 1 = 4 - 3 ✓ |
|
||
|
||
两轮过程：
|
||
|
||
**第一轮（快慢指针检测）：**
|
||
|
||
```
|
||
初始: slow=3(head), fast=3(head)
|
||
|
||
第1轮: slow→2(E), fast→0 （slow 走1步, fast 走2步）
|
||
第2轮: slow→0, fast=-4 （slow 走1步, fast 走2步）
|
||
第3轮: slow→-4, fast→2(E) （slow 走1步, fast 走2步）
|
||
第4轮: slow→2(E), fast→2(E) ← SLOW == FAST，相遇于 E ✗（巧合！）
|
||
|
||
⚠️ 本例恰好相遇于入口，但不代表总是如此。
|
||
换一组数据就能看出差异。
|
||
```
|
||
|
||
> [!note] 🤔 为什么本例的特殊情况会让人误解？
|
||
> 因为 x = 1（head 就是入口），慢指针只走了 4 步（刚好一圈）就和快指针相遇了，相遇点恰好是入口。让我们构造一个更一般的例子来观察：
|
||
>
|
||
> 假设链表 `1→2→3→4→5→(回2)`：
|
||
> - x = 1（head[1]→入口[2]）
|
||
> - 慢指针走 1+1=2 步到节点 3
|
||
> - 快指针走 4 步：1→3→5→3→? 最终也会在节点 3 相遇
|
||
> - 但从 head 走 x=1 步到 2，从相遇点 3 走 x=1 步到 4 ≠ 2
|
||
>
|
||
> 等等，让我重新计算：
|
||
>
|
||
> 慢指针 L = x + y = 1 + y，快指针 2L = 1 + y + n·r（r=4）
|
||
> 2(1+y) = 1+y+4n → 1+y = 4n → y = 4n-1
|
||
> n=1 时 y=3，即相遇点在入口往后数第3个节点 = 节点5
|
||
>
|
||
> 验证：慢指针走 1+3=4 步到节点5，快指针走8步也到节点5。✓
|
||
>
|
||
> **第二轮：** ptr1 从 head(1) 走 x=1 步到节点2（入口）；ptr2 从相遇点(5) 走 1 步到节点2（5→2，因为是环）。二者在节点2相遇！完美。
|
||
|
||
### 整体算法流程
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
START(["输入 head"]) --> BOUNDARY{"head == nil?"}
|
||
BOUNDARY -->|是| NOLOOP["返回 nil"]
|
||
BOUNDARY -->|否| ROUND1["⏩ 第一轮：快慢指针<br/>slow 每步1次, fast 每步2次"]
|
||
|
||
ROUND1 --> HASMEET{"是否相遇？"}
|
||
HASMEET -->|否| NOLOOP2["fast 触底 nil<br/>→ 无环，返回 nil"]
|
||
HASMEET -->|是| MEETPT["记录相遇点 meetNode"]
|
||
|
||
MEETPT --> ROUND2["⏩ 第二轮：双指针同速<br/>ptr1 = head, ptr2 = meetNode"]
|
||
ROUND2 --> SYNCLOOP{"ptr1 != ptr2?"}
|
||
SYNCLOOP -->|是| MOVE["ptr1++, ptr2++"]
|
||
MOVE --> SYNCLOOP
|
||
SYNCLOOP -->|否| ENTRY["🎯 ptr1/ptr2 就是环入口！"]
|
||
|
||
style NOLOOP fill:#ccc,stroke:#333
|
||
style NOLOOP2 fill:#ccc,stroke:#333
|
||
style ENTRY fill:#fd4,stroke:#333,stroke-width:3px
|
||
```
|
||
|
||
| 轮次 | 操作 | 时间复杂度 | 说明 |
|
||
|------|------|-----------|------|
|
||
| 第一轮 | 快指针每次 2 步，慢指针每次 1 步 | O(n) | 找到是否有环及相遇点 |
|
||
| 第二轮 | 两指针各 1 步，从 head 和相遇点出发 | O(n) | 找到环入口 |
|
||
| **合计** | — | **O(n)** | **空间 O(1)** |
|
||
|
||
> [!info] 📐 正确性证明总结
|
||
|
||
| 步骤 | 命题 | 依据 |
|
||
|------|------|------|
|
||
| 1 | 若有环，快慢指针必在环内相遇 | 每步距离缩短 1，最多 r 步 |
|
||
| 2 | 相遇时满足 x + y = n × r | 快指针速度是慢指针的两倍 |
|
||
| 3 | 从 head 走 x 步与从相遇点走 x 步汇于同一节点 | x = (n-1)r + (r-y) |
|
||
| 4 | 该节点即为环入口 | 从 head 往前走 x 步正好到入口 |
|
||
|
||
---
|
||
|
||
## 代码提示
|
||
|
||
```go
|
||
// ======== 第一轮：检测环，找相遇点 ========
|
||
slow, fast := head, head
|
||
for fast != nil && fast.Next != nil {
|
||
slow = slow.Next // 每次 1 步
|
||
fast = fast.Next.Next // 每次 2 步
|
||
if slow == fast { // 相遇！进入第二轮
|
||
break
|
||
}
|
||
}
|
||
|
||
// 没相遇 → 无环
|
||
if fast == nil || fast.Next == nil {
|
||
return nil
|
||
}
|
||
|
||
// ======== 第二轮：找入口 ========
|
||
ptr1 := head // 从头部出发
|
||
ptr2 := slow // 从相遇点出发
|
||
for ptr1 != ptr2 {
|
||
ptr1 = ptr1.Next
|
||
ptr2 = ptr2.Next
|
||
}
|
||
return ptr1 // 或 ptr2 —— 就是环入口
|
||
```
|
||
|
||
**Go 语言技巧：**
|
||
|
||
- Go 不支持 Python 风格的多赋值同时推进不同目标，需要分开写
|
||
- 利用 Go 的 `nil` 语义安全地检查边界条件
|
||
- 可以将第一轮的 `break` 后的检查合并为一行：`if slow == fast { ... } else { return nil }`
|
||
|
||
> [!tip] 🔑 Go 一行流写法（竞赛向）
|
||
> 利用 Go 的 for 语句特点，可以将两段逻辑合并：
|
||
|
||
```go
|
||
func detectCycle(head *ListNode) *ListNode {
|
||
for slow, fast := head, head; fast != nil && fast.Next != nil; {
|
||
slow = slow.Next
|
||
fast = fast.Next.Next
|
||
if slow == fast { // 相遇后立即切换模式
|
||
for head != slow { // ptr1=head, ptr2=slow 同速走
|
||
head = head.Next
|
||
slow = slow.Next
|
||
}
|
||
return head
|
||
}
|
||
}
|
||
return nil // fast 触底 → 无环
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
## 技巧
|
||
|
||
> [!tip] 🔑 核心模式：Floyd 环检测 + 对称映射
|
||
> 这道题的本质是利用代数推导出的**距离对称性**：从 head 到入口的距离 = 从相遇点到入口的距离。这可以看作一种"镜像翻转"——把线性前缀映射到了环形剩余路径上。
|
||
>
|
||
> **记忆口诀："一快一慢有环必遇，一回一遇入口必现。"**
|
||
|
||
> [!question] 🧠 深入思考：如果快指针每次走 3 步呢？
|
||
> 快指针走 k 步（k > 2），慢指针走 1 步，那么每步距离缩短 k-1。
|
||
> 相遇时有：(k-1)(x+y) = n·r。当 k=2 时，(x+y)=n·r，推导出 x = nr-y——简洁优美。
|
||
> 当 k=3 时，2(x+y)=n·r，推导出 x = nr/2 - y——可能不是整数，且无法直接使用"同速两步对走"的简单策略。
|
||
> 这也是为什么 Floyd 选 k=2（快2慢1）是最优设计的原因。
|
||
|
||
> [!danger] ⚠️ 常见错误
|
||
>
|
||
> 1. **忘记处理无环的情况**：第一轮结束后需要检查是否真的相遇了（`fast == nil || fast.Next == nil`），否则会把 `nil` 当成相遇点进入死循环。
|
||
> 2. **第二轮只用一个指针移动**：必须两个指针各走一步。
|
||
> 3. **把 `ptr1` 初始化成 `slow.Next`**：应该都是严格的一步一步走，`ptr1 = head`, `ptr2 = slow`。
|
||
|
||
> [!note] 🐹 Go 中的链表定义
|
||
> LeetCode 的 Go 环境内置如下结构体定义：
|
||
|
||
```go
|
||
type ListNode struct {
|
||
Val int
|
||
Next *ListNode
|
||
}
|
||
```
|
||
|
||
不需要手动定义，直接在解题中使用即可。
|
||
|
||
> [!info] 📊 两种方法对比
|
||
|
||
| 方法 | 时间复杂度 | 空间复杂度 | 备注 |
|
||
|------|-----------|-----------|------|
|
||
| 哈希集合记录访问过的节点 | O(n) | O(n) | 遍历每个节点，查 set |
|
||
| **Floyd 双指针 ⭐** | **O(n)** | **O(1)** | **最优，面试标配** |
|
||
|
||
> [!success] ✅ 相关题目串联
|
||
> - [25-环形链表](./25-环形链表.md) — 基础版：判断环的存在性
|
||
> - [22-相交链表](./22-相交链表.md) — 同样是双指针的经典应用
|
||
> - 剑指 Offer 23 — 环形链表的入口（完全相同的题目）
|
||
|
||
> [!warning] ⚠️ 面试注意事项
|
||
> - 面试时建议先推导一遍 x = n·r - y 的过程，展示你的分析能力
|
||
> - 面试官可能追问"如果没有环怎么办"——务必加上边界检查
|
||
> - 有些面试官会要求画图解法，提前准备好图示思维
|
||
> - 如果面试官要求你构建测试用例，至少准备：空链表、单节点有环/无环、head 就是入口、相遇点恰好在入口
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
### 方法一：哈希集合（O(n) 空间，不推荐）
|
||
|
||
```go
|
||
/**
|
||
* Definition for singly-linked list.
|
||
* type ListNode struct {
|
||
* Val int
|
||
* Next *ListNode
|
||
* }
|
||
*/
|
||
|
||
func detectCycle(head *ListNode) *ListNode {
|
||
seen := make(map[*ListNode]bool)
|
||
for node := head; node != nil; node = node.Next {
|
||
if seen[node] {
|
||
return node // 该节点已出现过 → 这是环入口
|
||
}
|
||
seen[node] = true
|
||
}
|
||
return nil // 走到末尾也没重复 → 无环
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
### 方法二：Floyd 环检测 + 对称映射 ⭐（最优 O(1) 空间）
|
||
|
||
```go
|
||
/**
|
||
* Definition for singly-linked list.
|
||
* type ListNode struct {
|
||
* Val int
|
||
* Next *ListNode
|
||
* }
|
||
*/
|
||
|
||
func detectCycle(head *ListNode) *ListNode {
|
||
// ======== 第一轮：快慢指针检测环 ========
|
||
slow, fast := head, head
|
||
for fast != nil && fast.Next != nil {
|
||
slow = slow.Next // 慢指针：每次走一步
|
||
fast = fast.Next.Next // 快指针：每次走两步
|
||
|
||
if slow == fast { // 在环内相遇了！
|
||
break // 跳出循环，进入第二轮
|
||
}
|
||
}
|
||
|
||
// 没相遇 → fast 触底 → 无环
|
||
if fast == nil || fast.Next == nil {
|
||
return nil
|
||
}
|
||
|
||
// ======== 第二轮：找环入口 ========
|
||
ptr1 := head // 指针1：从头节点出发
|
||
ptr2 := slow // 指针2：从相遇点出发
|
||
for ptr1 != ptr2 {
|
||
ptr1 = ptr1.Next
|
||
ptr2 = ptr2.Next
|
||
}
|
||
|
||
return ptr1 // ptr1 == ptr2，即为环入口节点
|
||
}
|
||
```
|
||
|
||
> [!tip] 🔑 精简写法（竞赛向）
|
||
|
||
```go
|
||
func detectCycle(head *ListNode) *ListNode {
|
||
for slow, fast := head, head; fast != nil && fast.Next != nil; {
|
||
slow = slow.Next
|
||
fast = fast.Next.Next
|
||
if slow == fast { // 相遇后切换模式
|
||
for head != slow {
|
||
head = head.Next
|
||
slow = slow.Next
|
||
}
|
||
return head
|
||
}
|
||
}
|
||
return nil
|
||
}
|
||
```
|
||
|
||
> [!success] ✅ 运行验证
|
||
> 这是 LeetCode 第 142 题，通过率约 46%，属于经典中等题。这道题的精妙之处在于**纯数学推导驱动算法设计**——没有复杂的技巧，仅靠一个简单的等式 x = n·r - y 就完成了从"检测环"到"定位入口"的跨越。建议在纸上画图推导一遍这个公式，理解后会感受到数学之美。
|