369 lines
13 KiB
Markdown
369 lines
13 KiB
Markdown
---
|
||
tags: ["LeetCode", "链表", "迭代", "递归", "虚拟头节点", "中等"]
|
||
create time: 2026-05-16 15:30
|
||
---
|
||
|
||
# 30-两两交换链表中的节点
|
||
|
||
## 题面
|
||
|
||
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。**你必须在不修改节点内部的值的情况下完成本题**（即，只能进行节点交换）。
|
||
|
||
**示例 1：**
|
||
|
||
```
|
||
输入：head = [1,2,3,4]
|
||
输出：[2,1,4,3]
|
||
```
|
||
|
||
**示例 2：**
|
||
|
||
```
|
||
输入：head = []
|
||
输出：[]
|
||
```
|
||
|
||
**示例 3：**
|
||
|
||
```
|
||
输入：head = [1]
|
||
输出：[1]
|
||
```
|
||
|
||
**提示：**
|
||
|
||
- 链表中节点的数目在范围 `[0, 100]` 内
|
||
- `0 <= Node.val <= 100`
|
||
|
||
---
|
||
|
||
## 思路
|
||
|
||
> [!question] 💡 核心洞察
|
||
> "两两交换"意味着我们要把 `A → B → C → D` 变成 `B → A → D → C`。每一次操作只涉及**两个一组**的节点对，组内互换、组间拼接。
|
||
|
||
### 关键问题：三指针协作
|
||
|
||
> [!warning] ⚠️ 最大陷阱
|
||
> 交换两个相邻节点时，如果先改了其中一个的 `Next`，就会**丢失另一个节点的引用**。必须像处理断链风险一样，用额外变量保存需要保留的地址。
|
||
|
||
### 一次交换的本质：四步重组
|
||
|
||
以交换节点 `A` 和 `B` 为例（`A` 在前，`B` 在后）：
|
||
|
||
```
|
||
交换前：... → prev → A → B → next → ...
|
||
↑ ↑ ↑
|
||
prev A.Next=B B.Next=next
|
||
```
|
||
|
||
要得到：
|
||
|
||
```
|
||
交换后：... → prev → B → A → next → ...
|
||
```
|
||
|
||
| 步骤 | 动作 | 对应代码 | 为什么必须先做这步？ |
|
||
|------|------|---------|------------------|
|
||
| ① | **记录后继**：`tmp = B.Next` | 防止 B.Next 被覆盖后丢失后续链表 | 如果不保存，后面一步会把 B.Next 改掉，再也找不到 C 了 |
|
||
| ② | **B 指向前驱**：`B.Next = A` | 建立 B→A 的反向连接 | 这是成对交换的核心——让后面的节点跑到前面去 |
|
||
| ③ | **A 指向后继**：`A.Next = tmp` | 让 A 接到下一组的首节点 | A 原来是前面的节点，现在需要连到未处理的部分 |
|
||
| ④ | **前驱接入 B**：`prev.Next = B` | 把整段接回主链 | 如果没有这一步，交换后的段落就从主链上脱落了 |
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
subgraph Before["交换前"]
|
||
P["prev"] --> A["A"]
|
||
A --> B["B"]
|
||
B --> N["next / C"]
|
||
end
|
||
|
||
subgraph Step1["① 记录后继: tmp = B.Next"]
|
||
S1["tmp ← C"]
|
||
end
|
||
|
||
subgraph Step2["② B.next = A"]
|
||
B2["B → A"]
|
||
end
|
||
|
||
subgraph Step3["③ A.next = tmp"]
|
||
A2["A → C"]
|
||
end
|
||
|
||
subgraph Step4["④ prev.next = B"]
|
||
P2["prev → B → A → C"]
|
||
end
|
||
|
||
Before --> S1 -.引导.-> Step2 -.引导.-> Step3 -.引导.-> Step4
|
||
|
||
style Before fill:#fff4e6,stroke:#f90
|
||
style Step4 fill:#d4edda,stroke:#28a
|
||
```
|
||
|
||
### 方法一：迭代法 + 虚拟头节点 ⭐（最优）
|
||
|
||
用一个**虚拟头节点** `dummy` 简化边界处理（特别是第一个节点对的交换），然后用一个指针 `prev` 滑动推进。
|
||
|
||
**不变量：** 每一轮循环开始时，`prev.Next` 始终是一个待交换节点对的第一个节点。
|
||
|
||
**执行流程演示（`head = [1,2,3,4]`）：**
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
Init["初始\ndummy→1→2→3→4\nprev=dummy"] --> Round1["第1轮: 交换 (1,2)\ndummy→2→1→3→4\nprev=1"]
|
||
Round1 --> Check1{"prev.Next != nil &&\nprev.Next.Next != nil?"}
|
||
Check1 -- 是 --> Round2["第2轮: 交换 (3,4)\ndummy→2→1→4→3\nprev=3"]
|
||
Round2 --> Check2{"prev.Next != nil &&\nprev.Next.Next != nil?"}
|
||
Check2 -- 否 --> Done["退出\nreturn dummy.Next ✅\n输出: [2,1,4,3]"]
|
||
|
||
style Init fill:#bbf,stroke:#333
|
||
style Round1 fill:#f9d,stroke:#333
|
||
style Round2 fill:#f9d,stroke:#333
|
||
style Done fill:#d4edda,stroke:#28a
|
||
```
|
||
|
||
逐步展开：
|
||
|
||
| 轮次 | 链表状态 | prev | 说明 |
|
||
|------|---------|------|------|
|
||
| 初始 | `dummy→1→2→3→4` | dummy | prev 从虚拟头出发 |
|
||
| 第 1 轮后 | `dummy→2→1→3→4` | 1 | 交换 (1,2)，prev 前进到 A(=1) |
|
||
| 第 2 轮后 | `dummy→2→1→4→3` | 3 | 交换 (3,4)，prev 前进到 A(=3) |
|
||
| 退出条件触发 | — | — | prev.Next == nil，退出循环 |
|
||
|
||
> [!question] 💡 引导思考：为什么 prev 要前进到 A（被交换的后那个节点）而不是 B？
|
||
> 因为交换完成后，B 跑到了前面，A 到了后面。下一组节点紧跟在 A 之后（`A.Next` 就是下一组的开头）。所以 `prev = A` 恰好让它在下一轮可以正确访问 `prev.Next`（下一组的第一个节点）。
|
||
|
||
**时间复杂度：O(n)** — 每个节点被访问常数次。
|
||
**空间复杂度：O(1)** — 只用了有限个指针变量。
|
||
|
||
### 方法二：递归法
|
||
|
||
递归的思路更抽象但极其简洁：**假设后半段已经处理好，我只管搞定第一对，然后把剩下的链接上去。**
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
subgraph Recursion["整体递归框架"]
|
||
R1["① newHead = head.Next\n(拿到第二节点)"] --> R2["② nextPair = newHead.Next\n(保存剩余部分起点)"]
|
||
R2 --> R3["③ newHead.Next = head\n(第二节点指回第一节点)"]
|
||
R3 --> R4["④ head.Next = swapPairs(nextPair)\n(第一节点接到递归结果)"]
|
||
R4 --> R5["返回 newHead ✅"]
|
||
end
|
||
|
||
style R1 fill:#bbf,stroke:#333
|
||
style R5 fill:#d4edda,stroke:#28a
|
||
```
|
||
|
||
**递的过程：** 一直深入到没有足够的节点继续配对时停止（`head == nil` 或 `head.Next == nil`），返回当前 head。
|
||
|
||
**归的过程：** 每层负责三件事：
|
||
1. 确定这一组的第二个节点为新的局部头
|
||
2. 把自己的两个节点交换好
|
||
3. 把第一对的尾部接到递归返回的结果上
|
||
|
||
以 `1→2→3→4` 为例的完整递归栈：
|
||
|
||
| 阶段 | head / newHead | nextPair | 执行的操作 | 返回值 |
|
||
|------|---------------|----------|-----------|--------|
|
||
| 递 | `head=3→4` | nil | 4.Next = 3；3.Next = swapPairs(nil) = nil | `4→3` |
|
||
| 基准 | `head=nil` | — | 直接返回 `nil` | `nil` |
|
||
| 归 | `head=1→2` | 3 | 2.Next = 1；1.Next = swapPairs(3→4) = 4→3 | `2→1→4→3` |
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
Base["基准: swapPairs(nil) → nil\n(不足一对，直接返回)"] --> L1["L1: head=3→4, newHead=4\n① 4.Next = 3\n② 3.Next = swapPairs(nil) = nil\n结果: 4→3→nil, 返回 4"]
|
||
L1 --> L2["L2: head=1→2, newHead=2\n① 2.Next = 1\n② 1.Next = swapPairs(3→4) = 4→3\n结果: 2→1→4→3, 返回 2 ✅"]
|
||
|
||
style Base fill:#eee,stroke:#999
|
||
style L1 fill:#bbf,stroke:#333
|
||
style L2 fill:#d4edda,stroke:#28a
|
||
```
|
||
|
||
> [!info] 🧠 递归的两个参数直觉
|
||
> - **函数签名**：`func swapPairs(head *ListNode) *ListNode` —— 传入一段链表，返回这段链表两两交换后的头
|
||
> - **假设成立**：调用 `swapPairs(rest)` 时，我们**假设它已经正确完成了任务**，只管拿到它的返回值来衔接
|
||
> - 这就是递归最强大的地方——不需要想全貌，每次只处理眼前的一对
|
||
|
||
**时间复杂度：O(n)** — 共 n/2 层递归，每层 O(1)。
|
||
**空间复杂度：O(n)** — 递归栈深度为 n/2。
|
||
|
||
---
|
||
|
||
## 代码提示
|
||
|
||
### 迭代法伪代码
|
||
|
||
```
|
||
// 创建虚拟头节点
|
||
dummy = &ListNode{Next: head}
|
||
prev = dummy
|
||
|
||
// 只要还有至少两个节点可以交换，就继续
|
||
while prev.Next != nil and prev.Next.Next != nil {
|
||
first = prev.Next // 待交换的第一个节点 (A)
|
||
second = prev.Next.Next // 待交换的第二个节点 (B)
|
||
third = second.Next // 第三组的起始节点
|
||
|
||
// 四步重组
|
||
second.Next = first // B → A
|
||
first.Next = third // A → C
|
||
prev.Next = second // prev → B → A → C
|
||
|
||
// prev 前进到已交换的第一对中的第二个（即 A）
|
||
prev = first
|
||
}
|
||
|
||
return dummy.Next
|
||
```
|
||
|
||
### 递归法伪代码
|
||
|
||
```
|
||
func swapPairs(head):
|
||
// 基准情况：不足两个节点，直接返回
|
||
if head == nil or head.Next == nil:
|
||
return head
|
||
|
||
// newHead 是第二节点，它就是这一对交换后的新头
|
||
newHead = head.Next
|
||
|
||
// 递归处理剩余部分
|
||
rest = swapPairs(newHead.Next)
|
||
|
||
// ① 第一对的第二个节点指向第一个节点
|
||
newHead.Next = head
|
||
// ② 第一个节点接到递归结果
|
||
head.Next = rest
|
||
|
||
return newHead
|
||
```
|
||
|
||
---
|
||
|
||
## 技巧
|
||
|
||
> [!tip] 🔑 "三步旋转"记忆法（迭代法核心）
|
||
> 两两交换本质上是在固定位置做一个**环形旋转**：`prev → A → B → next`。只需记住三条边的新方向：
|
||
> - `B.Next = A`（向后翻）
|
||
> - `A.Next = next`（跨过去）
|
||
> - `prev.Next = B`（接回来）
|
||
> 想象成一个三角形转了一圈。
|
||
|
||
> [!tip] 🔑 递归模板："搞一对，接尾巴"
|
||
> 适用于所有**分组处理**的链表问题：K 个一组翻转、奇偶重排等。模式为：
|
||
> 1. 检查是否还有足够节点继续分组
|
||
> 2. 用局部变量拿到每组的头和尾
|
||
> 3. 组内反转/调整
|
||
> 4. 组的头部接到递归结果
|
||
> 5. 返回新的头部
|
||
|
||
> [!warning] ⚠️ 常见错误 1：先改 A.Next 再取 B.Next
|
||
> 如果写成 `first.Next = second.Next` 再去取 `second.Next`，看起来没错。但如果不小心写成 `first.Next = nil` 或其他操作，后面再用 `second.Next` 就会出错。**建议：第一步总是先全部读取所需节点到局部变量中。**
|
||
|
||
> [!warning] ⚠️ 常见错误 2：prev 走错位置
|
||
> 交换完成后 prev 必须走到 A（原第一个节点，现在在第二位），而不是走到 B。因为 A 的 Next 指向下一组的开头，这样才能在下一轮正确定位。
|
||
|
||
> [!note] 🐹 Go 中的链表定义
|
||
> LeetCode 的 Go 环境内置如下结构体定义：
|
||
|
||
```go
|
||
type ListNode struct {
|
||
Val int
|
||
Next *ListNode
|
||
}
|
||
```
|
||
|
||
不需要手动定义，直接在解题中使用即可。
|
||
|
||
> [!info] 📊 两种方法对比
|
||
|
||
| 维度 | 迭代法 ⭐ | 递归法 |
|
||
|------|---------|--------|
|
||
| 时间复杂度 | O(n) | O(n) |
|
||
| 空间复杂度 | O(1) | O(n)（递归栈） |
|
||
| 代码行数 | 循环体约 7 行 | 核心逻辑约 6 行 |
|
||
| 直观程度 | **高**（一步步模拟交换过程） | 中等（需理解假设正确性） |
|
||
| 面试推荐 | ⭐⭐⭐ 首选 | ⭐⭐ 可作为进阶展示 |
|
||
| 适用场景 | 通用，无栈溢出风险 | 适合教学和理解分组思想 |
|
||
|
||
> [!success] ✅ 相关题目串联
|
||
> - 这题是后续更多**分组类链表操作**的基础模板：
|
||
> - [25-K 个一组翻转链表](./) — K 个一组的泛化版本
|
||
> - [奇偶链表](https://leetcode.com/problems/odd-even-linked-list/) — 按奇偶位置分组
|
||
> - 同一思想的变体还出现在 [数组的两两配对问题](./) 中
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
### 迭代法（虚拟头节点）⭐
|
||
|
||
```go
|
||
/**
|
||
* Definition for singly-linked list.
|
||
* type ListNode struct {
|
||
* Val int
|
||
* Next *ListNode
|
||
* }
|
||
*/
|
||
|
||
func swapPairs(head *ListNode) *ListNode {
|
||
dummy := &ListNode{Next: head} // 虚拟头节点，统一第一个节点对的边界处理
|
||
prev := dummy // prev 指向每一组待交换节点的前驱
|
||
|
||
for prev.Next != nil && prev.Next.Next != nil {
|
||
first := prev.Next // A：当前对的第一个节点
|
||
second := prev.Next.Next // B：当前对的第二个节点
|
||
third := second.Next // C：下一组的起始节点
|
||
|
||
// 四步重组：prev → B → A → C
|
||
second.Next = first // ① B 指向前驱对中的 A
|
||
first.Next = third // ② A 指向下一组的起始 C
|
||
prev.Next = second // ③ prev 接入 B，完成拼接
|
||
|
||
// prev 前进到已处理的这对中的 A 位置
|
||
// （A 现在是这对的末尾，Next 正好指向下一组的开头）
|
||
prev = first
|
||
}
|
||
|
||
return dummy.Next // 绕过虚拟头节点，返回真正的头节点
|
||
}
|
||
```
|
||
|
||
### 递归法
|
||
|
||
```go
|
||
/**
|
||
* Definition for singly-linked list.
|
||
* type ListNode struct {
|
||
* Val int
|
||
* Next *ListNode
|
||
* }
|
||
*/
|
||
|
||
func swapPairs(head *ListNode) *ListNode {
|
||
// 基准情况：空链表或只剩一个节点，无需交换
|
||
if head == nil || head.Next == nil {
|
||
return head
|
||
}
|
||
|
||
// newHead 是当前对的第二个节点，交换后将成为这一段的头
|
||
newHead := head.Next
|
||
|
||
// 保存剩余部分的起始点（即下一对的第一节点）
|
||
nextPair := newHead.Next
|
||
|
||
// ① 把第二节点接到第一节点前面
|
||
newHead.Next = head
|
||
|
||
// ② 递归处理剩余部分，并链接到当前第一节点的后面
|
||
head.Next = swapPairs(nextPair)
|
||
|
||
// newHead 成为整个链表的头
|
||
return newHead
|
||
}
|
||
```
|
||
|
||
> [!success] ✅ 运行验证
|
||
> 这是 LeetCode 第 24 题，通过率约 60%+。相比「删除倒数第 N 个节点」这道同级别的题目，"两两交换"的核心难度在于**多指针同时操作的顺序控制**——任何一个赋值的先后颠倒都可能导致断链或死循环。掌握这个四步重组模板后，面对任何涉及局部结构调整的链表问题都会更加从容。建议先用纸笔画出指针变化图，再动手编码。
|