---
tags: ["LeetCode", "链表", "堆", "分治", "优先队列", "困难"]
create time: 2026-05-18 15:30
---

# 34-合并 K 个升序链表

## 题面

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

**示例 1：**

```
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
```

**示例 2：**

```
输入：lists = []
输出：[]
```

**示例 3：**

```
输入：lists = [[]]
输出：[]
```

**提示：**

- k == lists.length
- 0 <= k <= 10^4
- 0 <= lists[i].length <= 500
- -10^4 <= lists[i][j] <= 10^4
- lists[i] 按 升序 排列
- lists[i].length 的总和不超过 10^4

---

## 思路

> [!question] 💡 引导思考
> 假设你已经会合并两个有序链表——现在让你合并 **K** 个有序链表，你会怎么做？——最直白的想法是：**先合并前两个，再用结果和第三个合并，依次类推**。这个思路可行吗？我们来分析一下。

### 方法零：暴力法 — 收集后排序 🐌（不推荐）

把所有链表中的所有节点值收集到一个切片中，排序后再重建链表。

| 步骤 | 操作 | 代价 |
|------|------|------|
| ① 遍历所有节点 | 把 Val 存入 `[]int` | O(N) |
| ② 排序 | Go 1.21+ 的 `slices.Sort()`（TimSort） | O(N log N) |
| ③ 重建链表 | 顺序创建节点 | O(N) |

其中 N 为所有链表的节点总数。

**时间复杂度：O(N log N)** — 排序主导。  
**空间复杂度：O(N)** — 存储所有节点值 + 新链表。

> [!note] 💬 虽然能 AC（总节点数 ≤ 10⁴），但完全没有利用"每个子链表已经有序"这一关键条件。面试中写出这个方案只能证明你理解题目，无法展示算法功底。接下来我们看更好的方案。

---

### 方法一：分治Merge（递归/迭代两阶段）⭐（推荐，面试首选）

> [!info] 🧠 核心洞察
> 合并两个有序链表是 O(m + n)。合并 K 个链表可以看作 **K-路归并**——就像归并排序的 merge 阶段，只不过同时参与 merge 的不是 2 个而是 K 个子序列。

#### 分治策略

如果我们每次只取两条链表来合并，那总共需要合并多少次呢？

| 阶段 | 剩余链表数 | 合并操作数 | 说明 |
|------|-----------|----------|------|
| 初始 | K | — | K 条独立链表 |
| 第 1 轮 | K/2 | K/2 | 两两配对合并 |
| 第 2 轮 | K/4 | K/4 | 上一步的结果继续两两合并 |
| ... | ... | ... | — |
| 最后 | 1 | 1 | 只剩一条，完成 ✅ |

共需 ⌈log₂K⌉ 轮，每轮所有节点恰好被访问一次。

```mermaid
flowchart TB
    subgraph Round1["🔄 第 1 轮：K → K/2"]
        A1["L1: 1→4→5"]
        A2["L2: 1→3→4"]
        A3["L3: 2→6"]
        
        M1["merge(L1,L2)\n→ 1→1→3→4→5"]
        B1["L4: 2→6"]
        
        A1 -->|"配对"| M1
        A2 -->|"配对"| M1
        A3 -->|"落单，直接保留"| B1
    end
    
    subgraph Round2["🔄 第 2 轮：K/2 → 1"]
        M2["merge(M1,B1)\n→ 1→1→2→3→4→4→5→6"]
    end
    
    M1 --> Round2
    B1 --> Round2
    
    style M2 fill:#4c4,color:white,stroke:#333,stroke-width:2px
    style M1 fill:#fff4e6,stroke:#f90
    style B1 fill:#e8f5e9,stroke:#28a
```

以 `[[1,4,5],[1,3,4],[2,6]]` 为例的分治过程：

```mermaid
flowchart LR
    subgraph "初始 K=3"
        L1["1→4→5"]
        L2["1→3→4"]
        L3["2→6"]
    end
    
    subgraph "第 1 轮: K→2"
        P1["merge(L1,L2)\n→ 1→1→3→4→5"]
        KEEP["L3 保留\n→ 2→6"]
    end
    
    subgraph "第 2 轮: K=1"
        FINAL["merge(P1,KEEP)\n→ 1→1→2→3→4→4→5→6 ✅"]
    end
    
    L1 --> P1
    L2 --> P1
    L3 --> KEEP
    P1 --> FINAL
    KEEP --> FINAL
    
    style FINAL fill:#4c4,color:white,stroke:#333,stroke-width:2px
```

#### 实现方式一：自顶向下递归（Divide & Conquer）

将问题不断二分，直到只剩 1 条或 0 条链表：

```go
func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }
    return divideAndConquer(lists, 0, len(lists)-1)
}

func divideAndConquer(lists []*ListNode, left, right int) *ListNode {
    // 基准情况：只有一个链表，直接返回
    if left == right {
        return lists[left]
    }
    
    mid := (left + right) / 2
    leftHalf := divideAndConquer(lists, left, mid)     // 合并左半部分
    rightHalf := divideAndConquer(lists, mid+1, right)  // 合并右半部分
    
    return mergeTwoLists(leftHalf, rightHalf)           // 合并两个有序链表
}
```

> [!tip] 🔑 这棵递归树的结构
> 
> ```
>                 [0,2]
>                /      \
>            [0,1]       [2,2]
>            /   \          |
>         [0,0] [1,1]     [2]
>          |      |         |
>         L1     L2        L3
> ```
>
> 这是一棵平衡二叉树——深度为 O(log K)，不会像退化版本那样出现栈溢出。

#### 实现方式二：迭代式逐轮合并

不依赖调用栈，显式地逐轮减少链表数量：

```go
func mergeKLists(lists []*ListNode) *ListNode {
    interval := 1
    for interval < len(lists) {
        for i := 0; i + interval < len(lists); i += 2 * interval {
            lists[i] = mergeTwoLists(lists[i], lists[i+interval])
        }
        interval *= 2
    }
    
    if len(lists) > 0 {
        return lists[0]
    }
    return nil
}
```

以 `[[1,4,5],[1,3,4],[2,6]]` 为例的迭代过程：

```mermaid
flowchart LR
    subgraph "初始状态"
        A["[1,4,5]"]
        B["[1,3,4]"]
        C["[2,6]"]
    end
    
    subgraph "interval=1: i+=2"
        R1["A=merge(A,B)\n→ [1,1,3,4,5]"]
        KEEP["C 不变\n→ [2,6]"]
    end
    
    subgraph "interval=2: i+=4"
        FIN["A=merge(R1,C)\n→ [1,1,2,3,4,4,5,6] ✅"]
    end
    
    A --> R1
    B --> R1
    C --> KEEP
    R1 --> FIN
    KEEP --> FIN
    
    style FIN fill:#4c4,color:white,stroke:#333,stroke-width:2px
```

逐步展开 `[interval=1, i=0]`：
- `lists[0] = merge(lists[0], lists[1])` → `merge([1,4,5], [1,3,4]) = [1,1,3,4,5]`
- `i += 2` → `i = 2`，`2 + 1 = 3 ≱ 3`，内层循环结束
- `interval *= 2` → `interval = 2`

接着 `[interval=2, i=0]`：
- `lists[0] = merge(lists[0], lists[2])` → `merge([1,1,3,4,5], [2,6]) = [1,1,2,3,4,4,5,6]`
- `i += 4` → `i = 4`，退出

#### 复杂度分析

```mermaid
flowchart TD
    subgraph "分治合并的分析"
        DEPTH["递归深度: log K 层"]
        
        subgraph "每层工作量"
            PER_LAYER["每层合并所有 N 个节点<br/>代价: O(N)"]
        end
        
        TOTAL["总代价: O(N) × log K = O(N log K)"]
    end
    
    DEPTH --> PER_LAYER --> TOTAL
    
    style TOTAL fill:#d4edda,stroke:#28a,stroke-width:2px
```

- **每层代价：O(N)** —— 无论有多少条链表在参与合并，所有节点的 total value 在每个层级只被访问一次。
- **层数：O(log K)** —— 每轮配对使链表数量减半。
- **总时间复杂度：O(N log K)** ✅

> [!info] 📊 K=10^4 时：log₂(10⁴) ≈ 13.3，即最多约 14 轮合并。  
> N ≤ 10⁴ 时：总操作量约 1.4 × 10⁵ 次比较，远优于暴力的 O(N²)。

**空间复杂度：O(log K)**（递归版）或 **O(1)**（迭代版）。

---

### 方法二：最小堆 / 优先队列 🏗️

> [!question] 💡 如果你需要维护一个集合中的"最小元素"，并且这个集合会动态增删，什么数据结构最高效？

答案是 **堆（Heap）**。它的插入和删除都是 O(log M)，查询最小值是 O(1)——正是本题的需求！

#### 核心思想

每一步都从 K 个链表的头节点中选出最小的那个，接入结果链表，然后把该链表的下一个节点放回堆中：

```mermaid
flowchart TD
    PUSH["将所有非空链表的头节点推入最小堆"]

    subgraph Loop["循环：直到堆为空"]
        EXTRACT["弹出堆顶<br/>(当前最小节点)"]
        APPEND["接入结果链表"]
        
        CHECK{"该节点有 Next 吗？"}
        INSERT["将 Next 推入堆"]
        
        EXTRACT --> APPEND --> CHECK
        CHECK -- "是" --> INSERT --> PUSH
        CHECK -- "否" --> EMPTY["堆中少了一个元素"]
        EMPTY --> CHECK
    end

    subgraph Done["终止"]
        RESULT["返回结果链表 ✅"]
    end
    
    PUSH --> Loop
    CHECK -. "堆空" .-> Done
    
    style RESULT fill:#4c4,color:white,stroke:#333,stroke-width:2px
```

以 `[[1,4,5],[1,3,4],[2,6]]` 为例：

| 步骤 | 堆内容（Val） | 弹出的节点 | 结果链表 |
|------|-------------|----------|---------|
| 初始化 | `[1, 1, 2]` | — | `dummy → ?` |
| 第 1 步 | `[1, 2, 4]` | ①（来自 L1） | `1` |
| 第 2 步 | `[1, 2, 3]` | ①（来自 L2） | `1→1` |
| 第 3 步 | `[2, 3, 4]` | ②（来自 L3） | `1→1→2` |
| 第 4 步 | `[3, 4, 4]` | ③（来自 L2） | `1→1→2→3` |
| 第 5 步 | `[4, 4, 6]` | ④（来自 L1） | `1→1→2→3→4` |
| 第 6 步 | `[4, 6]` | ④（来自 L2） | `1→1→2→3→4→4` |
| 第 7 步 | `[6, 5]` | ⑤（来自 L1） | `1→1→2→3→4→4→5` |
| 第 8 步 | `[6]` | ⑥（来自 L3） | `1→1→2→3→4→4→5→6` ✅ |

堆的操作次数 = 总节点数 N，每次 O(log K)。

#### Go 语言的 min-heap 实现

Go 标准库 `container/heap` 提供了通用的堆基础设施。你需要实现三个接口方法：`Len`、`Less`、`Swap`，以及自行封装 `Push` 和 `Pop`。

> [!warning] ⚠️ Go 的 interface{} vs 泛型
> 
> Go 1.18+ 引入了泛型，但 `container/heap` 仍基于 `interface{}`。对于 LeetCode Go 环境（通常是较新版本），可以使用以下通用 heap 模板：

```go
// IntHeap 是最小堆，存储链表指针，按 Val 排序
type IntHeap []*ListNode

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i].Val < h[j].Val } // 最小堆
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x any) {
    *h = append(*h, x.(*ListNode))
}

func (h *IntHeap) Pop() any {
    old := *h
    n := len(old)
    item := old[n-1]
    old[n-1] = nil // 避免内存泄漏
    *h = old[:n-1]
    return item
}
```

#### 完整代码

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

import (
	"container/heap"
)

// IntHeap 最小堆，按节点 Val 排序
type IntHeap []*ListNode

func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool {
	return h[i].Val < h[j].Val // 越小优先级越高
}
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x any) {
	*h = append(*h, x.(*ListNode))
}

func (h *IntHeap) Pop() any {
	old := *h
	n := len(old)
	item := old[n-1]
	old[n-1] = nil
	*h = old[:n-1]
	return item
}

func mergeKLists(lists []*ListNode) *ListNode {
	h := &IntHeap{}
	heap.Init(h)

	// ① 初始化：将所有非空链表的头节点推入堆
	for _, node := range lists {
		if node != nil {
			heap.Push(h, node)
		}
	}

	// 虚拟头节点
	dummy := &ListNode{}
	tail := dummy

	// ② 逐个弹出最小节点，并入结果链表
	for h.Len() > 0 {
		node := heap.Pop(h).(*ListNode) // 取出当前最小节点
		tail.Next = node
		tail = tail.Next

		// 如果该节点还有后继，将其推入堆
		if node.Next != nil {
			heap.Push(h, node.Next)
		}
	}

	return dummy.Next
}
```

**时间复杂度：O(N log K)** — 对 N 个节点各做一次 push/pop，每次 O(log K)。  
**空间复杂度：O(K)** — 堆中最多同时存储 K 个节点。

---

### 两种最优方法对比

```mermaid
flowchart LR
    subgraph DC["方法一：分治"]
        TIME1["O(N log K)"]
        SPACE1["O(1) 迭代 / O(log K) 递归"]
        CODE1["代码简洁"]
        PERF1["常数因子小"]
    end
    
    subgraph HP["方法二：最小堆"]
        TIME2["O(N log K)"]
        SPACE2["O(K)"]
        CODE2["需实现 heap 接口"]
        PERF2["适合动态流式输入"]
    end
    
    DC -->|"面试首选 ✅"| ANSWER["最优解"]
    HP -->|"工程适用 | 扩展性强"| ANSWER
    
    style ANSWER fill:#d4edda,stroke:#28a
```

| 维度 | 分治法（递归）⭐ | 最小堆法 🏗️ |
|------|---------------|------------|
| **时间复杂度** | O(N log K) | O(N log K) |
|**空间复杂度**| O(log K) 递归 / O(1) 迭代 | O(K) |
| **代码难度** | 低（复用两两合并） | 中（需实现 heap 接口） |
| **常数开销** | 更小（无 heap 操作） | 更大（push/pop 调度） |
| **适用场景** | 链表数组已知 | 链表逐个到来（流式数据） |
| **面试推荐度** | ⭐⭐⭐⭐⭐ | ⭐⭐⭐⭐ |

> [!success] ✅ 面试建议
> - **优先写分治法**：代码极简（仅需一行 merge 调用），容易推导，面试官满意
> - **作为加分项**提及堆做法：展示你对优先队列的理解及在流式场景的应用
> - 如果面试官追问"K 极大时怎么办"，可以讨论桶优化等更深层的思路

---

## 代码提示

### 分治迭代伪代码

```
interval = 1
while interval < K:
    for i = 0; i + interval < K; i += 2 * interval:
        lists[i] = merge(lists[i], lists[i + interval])
    interval *= 2

return lists[0] if K > 0 else nil
```

### 最小堆伪代码

```
h = 新建最小堆()

// 初始化：所有非空头入堆
for each node in lists:
    if node != nil:
        h.push(node)

dummy = new ListNode()
tail = dummy

while h is not empty:
    node = h.pop()              // 取出最小节点
    tail.Next = node
    tail = tail.Next
    
    if node.Next != nil:
        h.push(node.Next)       // 后继补入堆

return dummy.Next
```

---

## 技巧

> [!tip] 🔑 为什么 O(N log K) 优于 O(N log N)？
> 
> 暴力法排序的本质忽略了数据内在结构——每个子链表本身已是有序的。堆/分治法利用了这一点：只需要在 K 个候选者之间做决策（log K 级比较），而非对所有 N 个元素做全排序（log N 级比较）。当 K << N 时，差距巨大。
> 
> 举例：N = 10⁴, K = 100 → log K ≈ 6.6，log N ≈ 13.3——堆做法约为暴力的一半操作量；但当 N = 10⁶, K = 100 时，差距变为 10 倍以上。

> [!tip] 🔑 虚拟头节点（Dummy Node）万能公式
> 
> 遇到"构造链表"类题目，模板化的起手式：
> 
> ```
> dummy = new ListNode()
> tail = dummy
> // ... 循环中 tail.Next = newNode; tail = tail.Next ...
> return dummy.Next
> ```
> 
> 这条模式出现在：27-合并两个有序链表、此题、21-两数相加、83-删除排序链表中的重复元素、等等。**背下来，考场上一行就搞定边界处理。**

> [!note] 🔑 分治的迭代写法比递归写法精妙在哪？
> 
> 它直接在原数组 `lists` 上原地合并，不分配额外数组。关键在于 `i += 2 * interval`——每次跳过已合并的那一对，防止重复处理。这种"间隔倍增"的技巧在很多分治场景中都有应用。

> [!warning] ⚠️ Go 中 container/heap 的常见坑
> 
> 1. **Less 必须严格小于 `<`**，不能用 `<=`——否则相同值的节点顺序不确定，可能导致逻辑错误
> 2. **Pop 后要置 nil**：`old[n-1] = nil`，避免 Go GC 无法回收被弹出的旧引用造成内存泄漏
> 3. **Push/Pop 接收者是指针**：函数签名是 `(h *IntHeap)`，不是值类型

> [!tip] 🔑 边界情况的三种极端
> 
> | 输入 | 预期输出 | 处理要点 |
> |------|---------|---------|
> | `[]`（K = 0） | `nil` | 检查 `len(lists) == 0` |
> | `[[]]`（K = 1，空链表） | `nil` | 堆初始化时跳过 nil 节点 |
> | `[[], [], []]`（全空） | `nil` | 堆始终为空，直接返回 `dummy.Next` |

> [!info] 📊 三者的直观感受

| 方法 | 直觉 | 代码行数（含注释） | 面试白板友好度 |
|------|------|------------------|-------------|
| **暴力排序** | 最容易想到 | ~10 | ★★★ |
| **分治合并** | 自然推广两两合并 | ~15 | ★★★★★ |
| **最小堆** | 需要熟悉 heap 接口 | ~25 | ★★★★ |

---

## 代码

### 方法一：分治合并 ⭐

#### 递归实现

将问题不断二分，直到子问题只剩 0 或 1 条链表，回溯时逐层合并。由于 `lists` 在递归过程中是**只读的**，直接作为额外参数传递即可——Go 的函数栈帧很小，多一个切片头参数毫无影响，无需借助闭包增加认知负担：

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func mergeKLists(lists []*ListNode) *ListNode {
	if len(lists) == 0 {
		return nil
	}
	return divideAndConquer(lists, 0, len(lists)-1)
}

// divideAndConquer 二分合并 lists[left..right]
func divideAndConquer(lists []*ListNode, left, right int) *ListNode {
	if left == right { // 基准情况：只剩一条
		return lists[left]
	}
	
	mid := left + (right-left)/2
	leftHalf  := divideAndConquer(lists, left, mid)       // 左半 [left, mid]
	rightHalf := divideAndConquer(lists, mid+1, right)    // 右半 [mid+1, right]
	
	return mergeTwoLists(leftHalf, rightHalf)             // 两半回溯合并
}

// mergeTwoLists 合并两个有序链表（复用 27-合并两个有序链表的解法）
func mergeTwoLists(l1, l2 *ListNode) *ListNode {
	dummy := &ListNode{}
	tail := dummy

	for l1 != nil && l2 != nil {
		if l1.Val <= l2.Val {
			tail.Next = l1
			l1 = l1.Next
		} else {
			tail.Next = l2
			l2 = l2.Next
		}
		tail = tail.Next
	}

	if l1 != nil {
		tail.Next = l1
	} else {
		tail.Next = l2
	}

	return dummy.Next
}
```

**时间复杂度：** O(N log K)  
**空间复杂度：** O(log K)——递归栈深度等于分治树高度

---

#### 迭代实现

不依赖调用栈，显式地逐轮减少链表数量（原地合并）：

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func mergeKLists(lists []*ListNode) *ListNode {
	// 边界情况：没有链表需要合并
	if len(lists) == 0 {
		return nil
	}

	interval := 1
	for interval < len(lists) {
		// 本轮：每两个相距 interval 的链表互相合并
		for i := 0; i+interval < len(lists); i += 2 * interval {
			lists[i] = mergeTwoLists(lists[i], lists[i+interval])
		}
		interval *= 2 // 间隔翻倍，进入下一轮
	}

	// 最终 lists[0] 就是合并结果
	if len(lists) > 0 {
		return lists[0]
	}
	return nil
}
```

**时间复杂度：** O(N log K) — log K 轮合并，每轮遍历所有 N 个节点。  
**空间复杂度：** O(1) — 原地修改 lists 数组中的指针，不使用额外空间。

---

### 方法二：最小堆 / 优先队列

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

import (
	"container/heap"
)

// IntHeap 实现 container/heap 接口的最小堆，按节点 Val 排序
type IntHeap []*ListNode

func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i].Val < h[j].Val }
func (h IntHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x any) {
	*h = append(*h, x.(*ListNode))
}

func (h *IntHeap) Pop() any {
	old := *h
	n := len(old)
	item := old[n-1]
	old[n-1] = nil // 避免内存泄漏
	*h = old[:n-1]
	return item
}

func mergeKLists(lists []*ListNode) *ListNode {
	h := &IntHeap{}
	heap.Init(h)

	// ① 初始化：将所有非空链表的头节点推入堆
	for _, node := range lists {
		if node != nil {
			heap.Push(h, node)
		}
	}

	// 虚拟头节点
	dummy := &ListNode{}
	tail := dummy

	// ② 逐个弹出最小节点，并入结果链表
	for h.Len() > 0 {
		node := heap.Pop(h).(*ListNode) // 取出当前 Val 最小的节点
		tail.Next = node
		tail = tail.Next

		// 将该节点的后继推入堆，维持堆大小为 ≤ K
		if node.Next != nil {
			heap.Push(h, node.Next)
		}
	}

	return dummy.Next
}
```

**时间复杂度：O(N log K)** — 对 N 个节点各执行一次 heap.Push / heap.Pop，单次 O(log K)。  
**空间复杂度：O(K)** — 堆中同时存储最多 K 个节点指针。

---

> [!tip] 🔧 本地测试辅助函数

```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
}
```

> [!success] ✅ 运行验证
> 
> 这是 LeetCode 第 23 题，通过率约 45%+。作为链表难度的代表之作，它综合考察了两个重要范式：① **分治法**——通过递归/迭代两两合并降低问题规模；② **优先队列**——用堆动态维护多路有序流的"下一步"。两道解法都值得熟练掌握，面试中建议优先展示分治法，再补充堆方法作为拓展。

> [!info] 📎 相关题目串联
> - [27-合并两个有序链表](./27-合并两个有序链表.md) — 本问题的基础组件，合并两步直接复用
> - [28-两数相加](./28-两数相加.md) — 同样是链表加法思维，注意进位处理的差异
> - [33-排序链表](./33-排序链表.md) — 归并排序思想，与本问题的分治框架高度相似