361 lines
13 KiB
Markdown
361 lines
13 KiB
Markdown
---
|
||
tags: ["LeetCode", "链表", "双指针", "递归", "简单"]
|
||
create time: 2026-05-16 14:40
|
||
---
|
||
|
||
# 27-合并两个有序链表
|
||
|
||
## 题面
|
||
|
||
将两个 **升序** 链表合并为一个新的 **升序** 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
|
||
|
||
**示例 1：**
|
||
|
||
```
|
||
输入：l1 = [1,2,4], l2 = [1,3,4]
|
||
输出：[1,1,2,3,4,4]
|
||
```
|
||
|
||
**示例 2：**
|
||
|
||
```
|
||
输入：l1 = [], l2 = []
|
||
输出：[]
|
||
```
|
||
|
||
**示例 3：**
|
||
|
||
```
|
||
输入：l1 = [], l2 = [0]
|
||
输出：[0]
|
||
```
|
||
|
||
**提示：**
|
||
|
||
- 两个链表的节点数目范围是 `[0, 50]`
|
||
- `-100 <= Node.val <= 100`
|
||
- `l1` 和 `l2` 均按 **非递减顺序** 排列
|
||
|
||
---
|
||
|
||
## 思路
|
||
|
||
> [!question] 💡 引导思考
|
||
> 假设你面前有两张已经排好序的扑克牌，你会如何把它们合并成一张更大的有序牌堆？——每次比较两张牌的**最上面**那一张，取较小的放入结果中。这就是本题的核心思想。
|
||
|
||
### 方法一：迭代法 — 虚拟头节点 + 尾指针 ⭐（推荐）
|
||
|
||
维护一个**虚拟头节点** `dummy` 和一个**尾指针** `tail`：
|
||
|
||
| 变量 | 含义 |
|
||
|------|------|
|
||
| **dummy** | 虚拟头节点，`dummy.Next` 始终指向结果链表的真正头部 |
|
||
| **tail** | 当前已合并部分的最后一个节点，用于在末尾追加 |
|
||
|
||
**核心操作：** 每次比较 `l1.Val` 和 `l2.Val`，将较小的节点连接到 `tail.Next`，然后该链表的指针前进一步。
|
||
|
||
```mermaid
|
||
flowchart TB
|
||
subgraph Inputs["📥 输入：两条升序链表"]
|
||
L1["l1\n1→2→4→nil"]
|
||
L2["l2\n1→3→4→nil"]
|
||
end
|
||
|
||
subgraph Core["⚙️ 核心操作（循环内每轮重复）"]
|
||
CMP["比较 l1.Val vs l2.Val"]
|
||
Pick["选较小值节点"]
|
||
end
|
||
|
||
subgraph Output["📤 输出：结果链表（尾部追加）"]
|
||
Dummy["dummy (虚拟头节点)"]
|
||
Res["结果: 1→1→2→3→4→4→nil"]
|
||
end
|
||
|
||
L1 -->|当前 head| CMP
|
||
L2 -->|当前 head| CMP
|
||
CMP -->|l1.Val ≤ l2.Val?| Pick
|
||
Pick -->|连接到 tail.Next| Res
|
||
Res --> Dummy
|
||
|
||
style Dummy fill:#e0e0ff,stroke:#666,stroke-width:2px
|
||
style CMP fill:#fff4e6,stroke:#f90,stroke-width:2px
|
||
style Pick fill:#d4edda,stroke:#28a,stroke-width:2px
|
||
style Res fill:#e8f5e9,stroke:#4a4,stroke-width:1px
|
||
```
|
||
|
||
**图示执行流程：**
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
State0["初始\n---\ndummy → ?\nl1: 1→2→4\nl2: 1→3→4"] -->|"1≤1, 取 l1(1)"| State1["第 1 轮\n---\ndummy → [1]\nl1: 2→4\nl2: 1→3→4"]
|
||
State1 -->|"2>1, 取 l2(1)"| State2["第 2 轮\n---\ndummy → [1→1]\nl1: 2→4\nl2: 3→4"]
|
||
State2 -->|"2≤3, 取 l1(2)"| State3["第 3 轮\n---\ndummy → [1→1→2]\nl1: 4\nl2: 3→4"]
|
||
State3 -->|"4>3, 取 l2(3)"| State4["第 4 轮\n---\ndummy → [1→1→2→3]\nl1: 4\nl2: 4"]
|
||
State4 -->|"4≤4, 取 l1(4)"| State5["第 5 轮\n---\ndummy → [1→1→2→3→4]\nl1: nil\nl2: 4"]
|
||
State5 -->|"l1 空, 接 l2"| State6["收尾\n---\ndummy → [1→1→2→3→4→4] ✅"]
|
||
|
||
State6:::final
|
||
classDef final fill:#4c4,color:white
|
||
```
|
||
|
||
以示例 1（`l1 = [1,2,4]`, `l2 = [1,3,4]`）为例，逐步展开：
|
||
|
||
| 轮次 | 比较对象 | 较小值 | tail 连接 | l1 移动后 | l2 移动后 | 结果链表 |
|
||
|------|---------|--------|----------|----------|----------|---------|
|
||
| 初始 | — | — | dummy | 1→2→4 | 1→3→4 | `dummy → ?` |
|
||
| 第 1 轮 | l1.Val(1) vs l2.Val(**1**) | 相等，选 l1 | tail→l1(1) | 2→4 | 1→3→4 | `1_a` |
|
||
| 第 2 轮 | l1.Val(**2**) vs l2.Val(1) | 1 | tail→l2(1) | 2→4 | 3→4 | `1_a → 1_b` |
|
||
| 第 3 轮 | l1.Val(**2**) vs l2.Val(3) | 2 | tail→l1(2) | 4 | 3→4 | `1_a → 1_b → 2` |
|
||
| 第 4 轮 | l1.Val(**4**) vs l2.Val(3) | 3 | tail→l2(3) | 4 | 4 | `1→1→2→3` |
|
||
| 第 5 轮 | l1.Val(**4**) vs l2.Val(4) | 相等，选 l1 | tail→l1(4) | nil | 4 | `1→1→2→3→4` |
|
||
| l1 耗尽 | — | — | tail→l2(4) | nil | nil | `1→1→2→3→4→4` ✅ |
|
||
|
||
> [!info] 🧠 关键性质
|
||
> - 因为两个输入链表本身就是有序的，所以**每一步贪心选择较小的元素**就能保证全局有序
|
||
> - `dummy` 解决了"第一个节点没有前驱可连"的边界问题——统一了所有节点的处理逻辑
|
||
> - `tail` 只在末尾追加，永不回头修改，所以不需要反转操作
|
||
|
||
**当某个链表提前走完时：**直接将 `tail.Next` 指向另一个链表的剩余部分即可——因为剩余部分本身有序，无需额外处理。
|
||
|
||
**时间复杂度：O(m + n)** — 每个节点恰好被访问一次。
|
||
**空间复杂度：O(1)** — 只使用了常数个指针变量。
|
||
|
||
### 方法二：递归法（更优雅但占用栈空间）
|
||
|
||
> [!question] 💡 引导思考
|
||
> 合并两个有序链表时，**第一步做什么**——一定是把两个头节点中较小的那个作为结果链表的第一个节点。那第二步呢？
|
||
|
||
第二步是：**用剩下的部分重复同样的过程**。这正是递归的天然结构！
|
||
|
||
**递归关系：**
|
||
|
||
$$\text{merge}(l1, l2) = \begin{cases} l1 & \text{if } l2 == \text{nil} \\ l2 & \text{if } l1 == \text{nil} \\ l1.\text{Next} = \text{merge}(l1.\text{Next}, l2); \;\; return\; l1 & \text{if } l1.\text{Val} \leq l2.\text{Val} \\ l2.\text{Next} = \text{merge}(l1, l2.\text{Next}); \;\; return\; l2 & \text{otherwise} \end{cases}$$
|
||
|
||
**执行流程拆解**（以 `l1=[1,2,4]`, `l2=[1,3,4]` 为例）：
|
||
|
||
### 递：深入调用栈
|
||
|
||
每一层做出选择后，将较小节点的 `Next` 指向下一层递归的返回值，然后继续深入：
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
L1A["Merge(①, ①) → 选 l1(①)"] -->|"Next = Merge(2→4, 1→3→4)"| L1B["Merge(②, ①) → 选 l2(①)"]
|
||
L1B -->|"Next = Merge(2→4, 3→4)"| L1C["Merge(②, ③) → 选 l1(②)"]
|
||
L1C -->|"Next = Merge(4, 3→4)"| L1D["Merge(④, ③) → 选 l2(③)"]
|
||
L1D -->|"Next = Merge(4, ④)"| L1E["Merge(④, ④) → 选 l1(④)"]
|
||
L1E -->|"Next = Merge(nil, ④)"| L1F["Merge(nil, ④) ← 基准情况，返回 ④"]
|
||
|
||
style L1F fill:#f9d,stroke:#333,stroke-width:2px
|
||
style L1A fill:#bbf,stroke:#333
|
||
```
|
||
|
||
### 归：逐层拼接结果
|
||
|
||
在函数返回的过程中，上一层接收到的就是下一层的返回值——直接连到之前选择的节点上：
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
R1["Merge(nil, ④)\n返回: 4→nil"] --> R2["Merge(④, ④)\n4→Next=4→nil\n返回: 4→4→nil"]
|
||
R2 --> R3["Merge(④, ③)\n3→Next=4→4→nil\n返回: 3→4→4→nil"]
|
||
R3 --> R4["Merge(②, ③)\n2→Next=3→4→4→nil\n返回: 2→3→4→4→nil"]
|
||
R4 --> R5["Merge(②, ①)\n1→Next=2→3→4→4→nil\n返回: 1→2→3→4→4→nil"]
|
||
R5 --> R6["Merge(①, ①)\n1→Next=1→2→3→4→4→nil\n返回: 1→1→2→3→4→4 ✅"]
|
||
|
||
style R1 fill:#bbf,stroke:#333
|
||
style R6 fill:#4c4,color:white,stroke:#333,stroke-width:2px
|
||
```
|
||
|
||
> [!info] 🧠 递归与迭代的本质联系
|
||
> 递归版本中的 `l1.Next = mergeTwoLists(l1.Next, l2)` 或 `l2.Next = mergeTwoLists(l1, l2.Next)` 就是在做和迭代版 `tail.Next = smallerNode` 完全相同的操作——把当前最小的节点挂到结果后面。只是递归通过函数调用栈隐式地"记住"了上下文，而迭代版用显式的 `tail` 变量追踪当前位置。
|
||
|
||
**时间复杂度：O(m + n)** — 每层递归处理一个节点，共 m + n 层。
|
||
**空间复杂度：O(m + n)** — 递归调用栈深度等于节点总数。
|
||
|
||
---
|
||
|
||
## 代码提示
|
||
|
||
### 迭代法伪代码
|
||
|
||
```
|
||
dummy = &ListNode{} // 虚拟头节点
|
||
tail = dummy // 尾指针紧跟 dummy
|
||
|
||
for l1 != nil AND l2 != nil {
|
||
if l1.Val <= l2.Val {
|
||
tail.Next = l1 // 把 l1 接到结果末尾
|
||
l1 = l1.Next // l1 往前走一步
|
||
} else {
|
||
tail.Next = l2 // 把 l2 接到结果末尾
|
||
l2 = l2.Next // l2 往前走一步
|
||
}
|
||
tail = tail.Next // tail 也往前走一步（跟上）
|
||
}
|
||
|
||
// l1 或 l2 中至少有一个为空，接上非空的部分
|
||
if l1 != nil {
|
||
tail.Next = l1
|
||
} else {
|
||
tail.Next = l2
|
||
}
|
||
|
||
return dummy.Next // 跳过 dummy，返回真正的头节点
|
||
```
|
||
|
||
### 递归法伪代码
|
||
|
||
```
|
||
func merge(l1, l2):
|
||
if l1 == nil: return l2 // 基准情况 1
|
||
if l2 == nil: return l1 // 基准情况 2
|
||
|
||
if l1.Val <= l2.Val {
|
||
l1.Next = merge(l1.Next, l2)
|
||
return l1
|
||
} else {
|
||
l2.Next = merge(l1, l2.Next)
|
||
return l2
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
## 技巧
|
||
|
||
> [!tip] 🔑 虚拟头节点（Dummy Node）万能模板
|
||
> 凡是涉及"在链表头部插入/连接"的场景，优先考虑加 dummy。它能避免对首个节点写特殊逻辑，让循环体内保持统一的操作模式：`tail.Next = newnode; tail = tail.Next`。这个模式在「移除链表元素」「分隔链表」「奇偶链表」等题目中反复出现。
|
||
|
||
> [!note] 🔑 Go 语言细节：切片转链表的辅助函数
|
||
> 在本地测试时，你可能需要方便地在切片和链表之间转换：
|
||
|
||
```go
|
||
// sliceToList: 将切片转为链表，方便构造测试用例
|
||
func sliceToList(vals []int) *ListNode {
|
||
dummy := &ListNode{}
|
||
tail := dummy
|
||
for _, v := range vals {
|
||
tail.Next = &ListNode{Val: v}
|
||
tail = tail.Next
|
||
}
|
||
return dummy.Next
|
||
}
|
||
|
||
// listToSlice: 将链表转为切片，方便打印验证
|
||
func listToSlice(head *ListNode) []int {
|
||
var result []int
|
||
for head != nil {
|
||
result = append(result, head.Val)
|
||
head = head.Next
|
||
}
|
||
return result
|
||
}
|
||
```
|
||
|
||
> [!warning] ⚠️ 常见错误：忘记推进 tail
|
||
> 在连接 `tail.Next = smallerNode` 之后，一定要执行 `tail = tail.Next`。漏掉这步会导致后续所有节点都覆盖到同一个位置，最终结果只剩最后一个接入的节点。
|
||
|
||
> [!tip] 🔑 相等情况的选择
|
||
> 当 `l1.Val == l2.Val` 时，选哪个都可以，结果相同。但从递归视角看——先选 l1 意味着下一轮比较的是 `l1.Next` vs `l2`，先选 l2 则比较 `l1` vs `l2.Next`——虽然不影响最终结果，但在某些变体题（如稳定排序需求）中可能会有细微差异。
|
||
|
||
> [!note] 🐹 Go 中的链表定义
|
||
> LeetCode 的 Go 环境内置如下结构体定义：
|
||
|
||
```go
|
||
type ListNode struct {
|
||
Val int
|
||
Next *ListNode
|
||
}
|
||
```
|
||
|
||
不需要手动定义，直接在解题中使用即可。
|
||
|
||
> [!info] 📊 两种方法对比
|
||
|
||
| 方法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|
||
|------|-----------|-----------|------|------|
|
||
| **迭代法 ⭐** | **O(m + n)** | **O(1)** | 空间最优、无栈溢出风险 | 需要理解 dummy + tail 的配对使用 |
|
||
| 递归法 | O(m + n) | O(m + n) | 代码极短（4 行核心逻辑）、可读性高 | 栈空间消耗大；Go 不会尾递归优化，n 较大时可能栈溢出 |
|
||
|
||
> [!success] ✅ 相关题目串联
|
||
> - [82-删除排序链表中的重复元素 II](./82-删除排序链表中的重复元素-II.md) — 同一组有序链表的变种
|
||
> - [21-Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/) — 进阶：合并 K 个有序链表（分治 + 本题解法）
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
### 迭代法
|
||
|
||
```go
|
||
/**
|
||
* Definition for singly-linked list.
|
||
* type ListNode struct {
|
||
* Val int
|
||
* Next *ListNode
|
||
* }
|
||
*/
|
||
|
||
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
|
||
// 虚拟头节点：避免对第一个节点做特殊处理
|
||
dummy := &ListNode{}
|
||
tail := dummy // tail 始终指向结果链表的最后一个节点
|
||
|
||
// 只要两条链表都不为空，逐个比较、依次接入
|
||
for l1 != nil && l2 != nil {
|
||
if l1.Val <= l2.Val {
|
||
tail.Next = l1 // 将较小的 l1 节点接到结果末尾
|
||
l1 = l1.Next // l1 前进一步
|
||
} else {
|
||
tail.Next = l2 // 将较小的 l2 节点接到结果末尾
|
||
l2 = l2.Next // l2 前进一步
|
||
}
|
||
tail = tail.Next // tail 跟进，保持指向末尾
|
||
}
|
||
|
||
// 有一条链表走完后，直接把 tail 连接到另一条的剩余部分
|
||
// Go 的 nil 检查很直观：如果 l1 为空就接 l2，反之接 l1
|
||
if l1 != nil {
|
||
tail.Next = l1
|
||
} else {
|
||
tail.Next = l2
|
||
}
|
||
|
||
// 返回 dummy.Next（跳过虚拟头节点），即为合并后的真正头节点
|
||
return dummy.Next
|
||
}
|
||
```
|
||
|
||
### 递归法
|
||
|
||
```go
|
||
/**
|
||
* Definition for singly-linked list.
|
||
* type ListNode struct {
|
||
* Val int
|
||
* Next *ListNode
|
||
* }
|
||
*/
|
||
|
||
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
|
||
// 基准情况：一条链表为空，直接返回另一条
|
||
if l1 == nil {
|
||
return l2
|
||
}
|
||
if l2 == nil {
|
||
return l1
|
||
}
|
||
|
||
// 递归：选较小的头节点，它的 Next 指向合并剩余部分的结果
|
||
if l1.Val <= l2.Val {
|
||
l1.Next = mergeTwoLists(l1.Next, l2) // 递归处理 l1 的剩余部分
|
||
return l1
|
||
} else {
|
||
l2.Next = mergeTwoLists(l1, l2.Next) // 递归处理 l2 的剩余部分
|
||
return l2
|
||
}
|
||
}
|
||
```
|
||
|
||
> [!success] ✅ 运行验证
|
||
> 这是 LeetCode 第 21 题，通过率约 60%+。作为链表入门题的代表作，它完美展示了两个经典范式：① **迭代**——dummy + tail 的双指针尾部追加模式；② **递归**——"选出当前最小者 + 递归处理剩余"的分治思路。建议两个版本都手写一遍，体会"显式状态追踪"和"隐式调用栈"两种编程哲学的差异。
|