262 lines
9.8 KiB
Markdown
262 lines
9.8 KiB
Markdown
---
|
||
tags: ["LeetCode", "链表", "双指针", "快慢指针", "虚拟头节点", "中等"]
|
||
create time: 2026-05-16 15:00
|
||
---
|
||
|
||
# 29-删除链表的倒数第 N 个结点
|
||
|
||
## 题面
|
||
|
||
给你一个链表，删除链表的倒数第 `n` 个结点，并且返回链表的头结点。
|
||
|
||
**示例 1：**
|
||
|
||
```
|
||
输入：head = [1,2,3,4,5], n = 2
|
||
输出：[1,2,3,5]
|
||
```
|
||
|
||
**示例 2：**
|
||
|
||
```
|
||
输入：head = [1], n = 1
|
||
输出：[]
|
||
```
|
||
|
||
**示例 3：**
|
||
|
||
```
|
||
输入：head = [1,2], n = 1
|
||
输出：[1]
|
||
```
|
||
|
||
**提示：**
|
||
|
||
- 链表中结点的数目为 `sz`
|
||
- `1 <= sz <= 30`
|
||
- `0 <= Node.val <= 100`
|
||
- `1 <= n <= sz`
|
||
|
||
**进阶：** 你能尝试使用一趟扫描实现吗？
|
||
|
||
---
|
||
|
||
## 思路
|
||
|
||
> [!question] 💡 核心洞察
|
||
> 要删除倒数第 n 个节点，最直接的念头是——"先数总长，再找正数位置"。但这需要**两遍扫描**。进阶要求我们**一趟搞定**，怎么做到的？
|
||
|
||
关键在于：**用距离（gap）代替计数**。如果我们让两个指针之间始终保持 n 个节点的间隔，那么当快指针走到末尾时，慢指针自然就在目标位置。
|
||
|
||
### 关键问题：如何定位？
|
||
|
||
> [!warning] ⚠️ 最大陷阱
|
||
> 删除一个节点需要的是它的**前驱节点**——因为只有前驱才能修改 `Next` 指针把目标摘出去。如果慢指针恰好停在待删节点上，你就无从下手了。
|
||
|
||
所以我们的目标是：让慢指针最终停在**待删节点的前驱位置**。
|
||
|
||
### 方法一：快慢指针 + 虚拟头节点 ⭐（最优 — 一趟扫描）
|
||
|
||
维护两个指针 `fast` 和 `slow`，初始都指向一个**虚拟头节点** `dummy`（`dummy.Next = head`）。
|
||
|
||
**核心策略：** 先让 `fast` 走 n 步，然后 `fast` 和 `slow` 同时出发，每次各走一步。当 `fast` 到达最后一个节点时（`fast.Next == nil`），`slow` 恰好停在倒数第 n 个节点的前驱。
|
||
|
||
**为什么这样一定正确？**
|
||
|
||
> [!question] 💡 引导思考
|
||
> 假设链表长度为 sz，快指针领先 n 步。那么当快指针走完剩余路程时，它走了多少步？慢指针呢？它们之间的距离保持了几步？
|
||
|
||
快指针再走 `sz - n` 步会到达**最后一个节点**（而非越过边界）。循环条件 `fast.Next != nil` 保证在快指针停在尾节点时立即终止。此时慢指针也恰好走了 `sz - n` 步。由于 `dummy` 是第 0 位，`dummy → slow` 的距离就是 `sz - n`——这意味着 slow 指向的是正数第 `sz - n` 个节点，即倒数第 `n + 1` 个节点，正是待删节点的前驱。
|
||
|
||
关键不变量：**从 fast 先走 n 步之后起，slow 永远比 fast 落后 n 个节点**。这 n 的间隔全程保持不变，直到循环结束。
|
||
|
||
**图示执行流程：**
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
subgraph Init["第一步：fast 先走 n 步（n=2）"]
|
||
D["dummy"] -->|"slow"| A["1"]
|
||
A --> B["2"]
|
||
B --> C["3"]
|
||
C --> D2["4"]
|
||
D2 --> E["5"]
|
||
F["fast"] -.走2步.-> B
|
||
end
|
||
|
||
subgraph Sync["第二步：fast & slow 同步前进（直到 fast == 尾节点）"]
|
||
B -->|"slow→1, fast→3"| G["slow: 1 / fast: 3"]
|
||
G -->|"slow→2, fast→4"| H["slow: 2 / fast: 4"]
|
||
H -->|"slow→3, fast→5"| I["slow: 3 / fast: 5"]
|
||
end
|
||
|
||
subgraph Done["结束：fast==尾节点, slow在倒数第 n+1 个（待删前驱）"]
|
||
I -->|"fast.Next==nil, 退出"| K["slow指向3\n删除slow.Next(4)\n1→2→3→5 ✅"]
|
||
end
|
||
|
||
Init --> Sync --> Done
|
||
|
||
classDef done fill:#4c4,color:white
|
||
class K done
|
||
```
|
||
|
||
逐步展开（以 `head = [1,2,3,4,5], n = 2` 为例）：
|
||
|
||
| 阶段 | dummy | slow | fast | 说明 |
|
||
|------|--------|------|------|------|
|
||
| 初始 | → 1→2→3→4→5 | dummy | dummy | 都从虚拟头节点出发 |
|
||
| fast 走 n=2 步后 | → 1→2→3→4→5 | dummy | **2** | fast 跳过 1、2，停在 2 |
|
||
| 第 1 轮同步 | → 1→2→3→4→5 | **1** | **3** | 各走一步（fast.Next=3 ≠ nil） |
|
||
| 第 2 轮同步 | → 1→2→3→4→5 | **2** | **4** | 各走一步（fast.Next=4 ≠ nil） |
|
||
| 第 3 轮同步 | → 1→2→3→4→5 | **3** | **5** | 各走一步（fast.Next=5 ≠ nil） |
|
||
| 循环终止 | — | **3** | **5** | fast.Next == nil，退出循环 |
|
||
| 删除操作 | — | 指向 3 | — | `slow.Next = slow.Next.Next`，删除节点 4 |
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
Before["删除前\n1→2→3→4→5\n ↑slow\n ↑slow.Next\n ↑slow.Next.Next\n \ndelete slow.Next"] --> After["删除后\n1→2→3→5\n ↑slow.Next 指向 5 ✅"]
|
||
|
||
style Before fill:#fff4e6,stroke:#f90
|
||
style After fill:#d4edda,stroke:#28a
|
||
```
|
||
|
||
> [!info] 🧠 为什么用 `dummy` 能优雅处理所有边界？
|
||
> - **删除头节点**：如 `n = 5`（删除 1），此时 `dummy` 先走 5 步刚好到 `nil`，`slow` 还在 `dummy`，`slow.Next = slow.Next.Next` 删除的就是节点 1。
|
||
> - **删除尾节点**：如 `n = 1`（删除 5），此时 `slow` 停在节点 4，正常删除。
|
||
> - **单节点链表**：如 `head = [1], n = 1`，结果直接是空链表。
|
||
|
||
**时间复杂度：O(n)** — 每个节点最多被访问一次。
|
||
**空间复杂度：O(1)** — 只用了两个指针变量。
|
||
|
||
---
|
||
|
||
## 代码提示
|
||
|
||
### 快慢指针伪代码
|
||
|
||
```
|
||
// 第一步：创建虚拟头节点
|
||
dummy = &ListNode{Next: head}
|
||
slow = dummy
|
||
fast = dummy
|
||
|
||
// 第二步：fast 先走 n 步
|
||
for i = 0; i < n; i++ {
|
||
fast = fast.Next
|
||
}
|
||
|
||
// 第三步：fast 和 slow 同步前进，直到 fast 到达最后一个节点
|
||
for fast.Next != nil {
|
||
slow = slow.Next
|
||
fast = fast.Next
|
||
}
|
||
|
||
// 第四步：通过 slow 的 Next 跳过待删节点
|
||
slow.Next = slow.Next.Next
|
||
|
||
return dummy.Next
|
||
```
|
||
|
||
### 图解关键步骤
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
Step1["dummy 节点\n防止删除头节点时需要特殊判断"] --> Step2["fast 先走 n 步\n制造 n 的间隔"]
|
||
Step2 --> Step3["同步前进\nfast 到头时\nslow 恰好在倒数第 n+1 个"]
|
||
Step3 --> Step4["跳过待删节点\nslow.Next = slow.Next.Next"]
|
||
|
||
style Step1 fill:#bbf,stroke:#333
|
||
style Step2 fill:#f9d,stroke:#333
|
||
style Step3 fill:#ffd700,stroke:#333
|
||
style Step4 fill:#d4edda,stroke:#28a
|
||
```
|
||
|
||
---
|
||
|
||
## 技巧
|
||
|
||
> [!tip] 🔑 快慢指针"间隔法"通用模式
|
||
> "让快指针先走 k 步，然后一起走"是一个极其通用的模板。它解决的问题范式是：**找到与末尾有固定距离的某个位置**。除了本题（倒数第 n 个），还衍生出：
|
||
> - 链表的中间节点（k = n/2）
|
||
> - 环形链表的入口（稍作变形）
|
||
> - 排序数组中的差值对（类似思想扩展到数组）
|
||
|
||
> [!warning] ⚠️ 常见错误 1：忘记加虚拟头节点
|
||
> 如果不用 `dummy`，删除头节点（如 `n = sz`）时需要单独处理。加上 `dummy` 后，所有节点都被"右移了一位"，统一由 `slow.Next.Next` 处理。
|
||
|
||
> [!warning] ⚠️ 常见错误 2：fast 提前为空
|
||
> 当 n = sz 时，fast 走完 n 步后正好等于 `nil`。这时第三个循环（同步前进）不会执行，直接进入第四步——这正是正确的行为！不要误判为错误。
|
||
|
||
> [!note] 🔑 两遍扫描解法（辅助理解）
|
||
> 虽然不满足进阶要求，但两遍扫描的思路更直观：
|
||
> ① 第一遍遍历求长度 len；② 第二遍从头走到第 `len - n` 个节点的位置并删除。这种方法的优势是更容易扩展——比如你想删除倒数第 n ~ m 个节点时，比快慢指针更容易改写。**面试时可以先说两遍扫描的方案展示理解，再用快慢指针优化到一遍。**
|
||
|
||
> [!note] 🐹 Go 中的链表定义
|
||
> LeetCode 的 Go 环境内置如下结构体定义：
|
||
|
||
```go
|
||
type ListNode struct {
|
||
Val int
|
||
Next *ListNode
|
||
}
|
||
```
|
||
|
||
不需要手动定义，直接在解题中使用即可。
|
||
|
||
> [!info] 📊 两种扫描方式对比
|
||
|
||
| 维度 | 两遍扫描 | 一遍扫描（快慢指针）⭐ |
|
||
|------|---------|---------------------|
|
||
| 时间复杂度 | O(n)（两次遍历） | O(n)（一次遍历） |
|
||
| 空间复杂度 | O(1) | O(1) |
|
||
| 直观程度 | 非常直观 | 需要理解"间隔不变量" |
|
||
| 面试官满意度 | 合格，但不加分 | 优秀，满足进阶要求 |
|
||
| 适用场景 | 无法保证单次扫描时可用 | 绝大多数链表问题的首选 |
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
```go
|
||
/**
|
||
* Definition for singly-linked list.
|
||
* type ListNode struct {
|
||
* Val int
|
||
* Next *ListNode
|
||
* }
|
||
*/
|
||
|
||
func removeNthFromEnd(head *ListNode, n int) *ListNode {
|
||
// 虚拟头节点：消除"删除头节点需要特殊处理"的边界情况
|
||
dummy := &ListNode{Next: head}
|
||
slow := dummy
|
||
fast := dummy
|
||
|
||
// 快指针先走 n 步，与慢指针拉开 n 的距离
|
||
for i := 0; i < n; i++ {
|
||
fast = fast.Next
|
||
}
|
||
|
||
// 快慢指针同步前进，直到 fast 到达最后一个节点
|
||
for fast.Next != nil {
|
||
slow = slow.Next
|
||
fast = fast.Next
|
||
}
|
||
|
||
// slow 现在停在倒数第 n 个节点的前驱
|
||
// slow.Next = slow.Next.Next 直接跳过待删节点
|
||
slow.Next = slow.Next.Next
|
||
|
||
return dummy.Next // 绕过虚拟头节点，返回真正的头节点
|
||
}
|
||
```
|
||
|
||
> [!success] ✅ 运行验证
|
||
> 这是 LeetCode 第 19 题，通过率约 40%+。看似简单的题目恰恰最能检验对链表操作的熟练度——虚拟头节点是否本能地想到、快慢指针的间隔不变量是否能清晰解释。这道题是后续更多复杂链表题目的基础：反转链表的一部分、合并 K 个有序链表、链表的 K 逆序等都依赖同样的"间隔控制"思想。建议配合 Mermaid 图示手写 2-3 遍，直到形成肌肉记忆。
|
||
|
||
> [!note] 🔗 相关题目串联
|
||
> - [141-环形链表](./25-环形链表.md) — 另一个经典的双指针应用
|
||
> - [142-环形链表 II](./26-环形链表 II.md) — 快慢指针找环入口
|
||
> - [23-反转链表](./23-反转链表.md) — 链表基础操作
|
||
> - [24-两数相加](./28-两数相加.md) — 链表遍历的高级应用
|
||
> - [30-两两交换链表中的节点](./30-两两交换链表中的节点.md) — 多指针协作的经典题目
|