合并 K 个有序链表（Merge K Sorted Lists）
力扣第 23 题。给 K 条有序链表，合并成一条有序链表。
先从最简单的情况建立直觉
合并 2 条（力扣 21 题）是基础，双指针一遍扫：
cpp
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (l1 && l2) {
if (l1->val <= l2->val) { tail->next = l1; l1 = l1->next; }
else { tail->next = l2; l2 = l2->next; }
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
return dummy.next;
}
K 条的问题就是如何高效扩展这个思路。
解法一：最小堆（优先队列）⭐ 最直观
每次从 K 个链表的当前头节点中取最小值，用堆来维护这个”K选1″的过程。
cpp
ListNode* mergeKLists(vector<ListNode*>& lists) {
// 小根堆：比较节点值
auto cmp = [](ListNode* a, ListNode* b) {
return a->val > b->val; // 注意：greater → 小根堆
};
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
// 把每条链表的头节点入堆
for (ListNode* node : lists) {
if (node) pq.push(node);
}
ListNode dummy(0);
ListNode* tail = &dummy;
while (!pq.empty()) {
ListNode* node = pq.top(); pq.pop();
tail->next = node;
tail = tail->next;
if (node->next) pq.push(node->next); // 把后继入堆
}
return dummy.next;
}
复杂度： 时间 O(N log K)，空间 O(K)。N 是节点总数，每个节点进出堆一次，每次堆操作 O(log K)。
解法二：分治合并（代码更简洁，性能相同）⭐
把 K 条链表两两配对合并，每轮减半，像归并排序一样。
cpp
ListNode* mergeKLists(vector<ListNode*>& lists) {
int n = lists.size();
if (n == 0) return nullptr;
int step = 1;
while (step < n) {
for (int i = 0; i + step < n; i += step * 2) {
lists[i] = mergeTwoLists(lists[i], lists[i + step]);
}
step *= 2;
}
return lists[0];
}
走一遍例子（K=4）：
初始: [L0, L1, L2, L3]
step=1: L0=merge(L0,L1), L2=merge(L2,L3)
→ [L01, L1, L23, L3]
step=2: L0=merge(L01,L23)
→ [L0123, ...]
返回 lists[0]
为什么不能一条条顺序合并？
顺序合并: merge(merge(merge(L0,L1), L2), L3) 每次合并的链表越来越长，总代价 O(NK) 分治合并: 每轮 N 个节点各被合并一次，共 log K 轮 总代价 O(N log K) ← 差了一个数量级
复杂度： 时间 O(N log K)，空间 O(log K)（递归栈，若用迭代版则 O(1)）。
两种最优解法对比
| 最小堆 | 分治合并 | |
|---|---|---|
| 时间 | O(N log K) | O(N log K) |
| 空间 | O(K) | O(log K) 或 O(1) |
| 代码量 | 稍多 | 少，复用 mergeTwoLists |
| 扩展性 | 堆支持动态增删链表 | 静态列表更优 |
| 面试推荐 | 考察堆的使用 | 考察分治思维 |
两种都要掌握，面试时先说堆的思路，再说分治，展示你知道两种路径。
串联前面的知识
这道题是链表题的综合题，融合了：
- 合并两条有序链表（子问题）
- 最小堆/优先队列（高效选最小）
- 分治思想（把 O(NK) 压成 O(N log K)）
能把这三点讲清楚，链表这块基本就没有短板了。