leetcode-go/链表/27-合并两个有序链表.md

---
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 的双指针尾部追加模式；② **递归**——"选出当前最小者 + 递归处理剩余"的分治思路。建议两个版本都手写一遍，体会"显式状态追踪"和"隐式调用栈"两种编程哲学的差异。