778 lines
21 KiB
Markdown
778 lines
21 KiB
Markdown
---
|
||
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) — 归并排序思想，与本问题的分治框架高度相似
|