LeetCode 23困难堆 · 分治
合并 K 个升序链表 图解题解
K 条已经排好序的链表，怎样合并得最快？淘汰赛思路，log K 轮搞定。
合并 K 条有序链表，就像淘汰赛：两两配对，每对用双指针比头节点、谁小接谁合成一条，本轮 K 条变成 K/2 条；下一轮再两两合，log K 轮后汇成一条。每个节点在整个过程里只被碰 log K 次，比把所有节点倒进数组重排更快，而且充分利用了「每条链本来就有序」这个信息。
这道题到底在问什么
给 K 条升序链表，把它们合并成一条升序链表返回。
- 链表 A
- 1 → 4 → 5
- 链表 B
- 1 → 3 → 4
- 链表 C
- 2 → 6
- 输出
- 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6
最优解：一步一步想明白
- 3把全部节点倒进数组排一遍能做，但完全没利用「每条本来就有序」这个大便宜——重排是 O(N log N)，还白白丢掉了有序信息。
- 4转折：把 K 条捉对合并——合并两条有序链表我们是会的(比头节点，谁小接谁)。两两合完再两两合，像淘汰赛，log k 轮就汇成一条。每个节点每轮只被碰一次，所以是 O(N log k)，比重排更快。
- 5p1=A头1, p2=B头1先合并 A、B。p1 指 A 头 1，p2 指 B 头 1，结果链表(下方)还空着(虚线占位)。挂个 dummy 哨兵当结果起点，开始比头。
- 6p1 前进, 结果=1两个头都是 1，1 ≤ 1 取 A 的 1(一样大先接谁都行)接进结果，p1 前进到 4。结果链表长出第一个 1，tail 指向它。
- 7p2 前进, 结果=1→1现在比 A 的 4 和 B 的 1：4 大于 1，取 B 的 1，p2 前进到 3。结果：1 → 1。
- 8p2 前进, 结果=1→1→3A 的 4 仍比 B 的 3 大：4 大于 3，取 B 的 3，p2 前进到 4。结果：1 → 1 → 3。谁小接谁，指针各自往后爬。
- 9p1 前进, 结果…→4这回 A、B 头都是 4：4 ≤ 4 取 A 的 4，p1 前进到 5。结果：1 → 1 → 3 → 4。
- 10p2 到头, 结果…→4比 A 的 5 和 B 的 4：5 大于 4，取 B 的 4，p2 走到头——B 用完了。结果：1 → 1 → 3 → 4 → 4。
- 11A 剩 5 直接接关键负例：一条先走空(B 空)，就不必再逐个比了——把另一条剩下的整段(A 的 5)直接接到结果尾巴。结果：1 → 1 → 3 → 4 → 4 → 5。
- 12得到 6 节点有序链A、B 合成了 1→1→3→4→4→5。这就是「合并两条」的一整轮。下一轮拿这个结果再和 C=[2→6] 合并，还是同一套：比头、接小的，最终汇成 1→1→2→3→4→4→5→6。
- 15面对「合并 K 个」别慌：把它拆成你已经会的「合并两个」，再用分治两两推进。或者用小顶堆同时盯住 K 个头，每次弹最小，也是 O(N log k)。
- 20把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。
⚠️ 容易写错的地方
✗ 错：把所有节点收集再排序 O(N log N)，或逐条挨个合 O(Nk)
✓ 对：两两合并 / 小顶堆，O(N log k)
重排丢了「已有序」信息、逐条合让早期节点被反复扫；分治或堆才把 k 压成 log k
✗ 错：堆里只放 (val, node)
✓ 对：放 (val, i, node)，加个序号 i
val 相等时 Python 会去比 node 对象、报 TypeError；塞个唯一序号当第二关键字打破平局
✗ 错：分治忘了写 l==r 基例（单条链没人返回）
✓ 对：区间只剩一条(l==r)时直接 return v[l]
分治按下标对半拆，递归到只剩一条链时就是答案本身；漏掉这个基例会一直拆到越界。奇数条由此自然处理，无需特判落单。
完整代码（Python / C++ / Java）
Python
class Solution:
def mergeKLists(self, lists):
if not lists: return None
if len(lists) == 1: return lists[0]
mid = len(lists) // 2
left = self.mergeKLists(lists[:mid]) # 左半递归合成一条
right = self.mergeKLists(lists[mid:]) # 右半递归合成一条
return self.mergeTwo(left, right) # 再合并这两条
def mergeTwo(self, a, b): # 合并两条有序链(LC21)
dummy = cur = ListNode(0)
while a and b:
if a.val <= b.val: cur.next, a = a, a.next
else: cur.next, b = b, b.next
cur = cur.next
cur.next = a or b # 残段整条接上
return dummy.nextC++
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) return nullptr;
return merge(lists, 0, lists.size() - 1);
}
ListNode* merge(vector<ListNode*>& v, int l, int r) {
if (l == r) return v[l];
int m = (l + r) / 2;
return mergeTwo(merge(v, l, m), merge(v, m + 1, r));
}
ListNode* mergeTwo(ListNode* a, ListNode* b) {
ListNode dummy(0); ListNode* cur = &dummy;
while (a && b) {
if (a->val <= b->val) { cur->next = a; a = a->next; }
else { cur->next = b; b = b->next; }
cur = cur->next;
}
cur->next = a ? a : b;
return dummy.next;
}
};Java
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) return null;
return merge(lists, 0, lists.length - 1);
}
ListNode merge(ListNode[] v, int l, int r) {
if (l == r) return v[l];
int m = (l + r) / 2;
return mergeTwo(merge(v, l, m), merge(v, m + 1, r));
}
ListNode mergeTwo(ListNode a, ListNode b) {
ListNode dummy = new ListNode(0), cur = dummy;
while (a != null && b != null) {
if (a.val <= b.val) { cur.next = a; a = a.next; }
else { cur.next = b; b = b.next; }
cur = cur.next;
}
cur.next = a != null ? a : b;
return dummy.next;
}
}套路模板 · 小顶堆解法（背下来）
import heapq
class Solution:
def mergeKLists(self, lists):
h = [(node.val, i, node) for i, node in enumerate(lists) if node]
heapq.heapify(h) # K 个头进堆
dummy = cur = ListNode(0)
while h:
val, i, node = heapq.heappop(h) # 弹出全局最小头
cur.next = node; cur = node
if node.next:
heapq.heappush(h, (node.next.val, i, node.next))
return dummy.nextclass Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
auto cmp = [](ListNode* a, ListNode* b){ return a->val > b->val; };
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
for (ListNode* node : lists) if (node) pq.push(node);
ListNode dummy(0);
ListNode* cur = &dummy;
while (!pq.empty()) {
ListNode* node = pq.top(); pq.pop();
cur->next = node; cur = cur->next;
if (node->next) pq.push(node->next);
}
return dummy.next;
}
};class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode node : lists) if (node != null) pq.offer(node);
ListNode dummy = new ListNode(0), cur = dummy;
while (!pq.isEmpty()) {
ListNode node = pq.poll();
cur.next = node; cur = cur.next;
if (node.next != null) pq.offer(node.next);
}
return dummy.next;
}
}复杂度
时间复杂度
O(N log k)
N 个节点，每轮全碰一次、共 log k 轮
空间复杂度
O(log k)
分治递归栈深度 log k（合并本身原地接指针）
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 合并 K 个升序链表 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么堆大小是 K 不是 N？+
堆里只放 K 条链各自的当前头，最多 K 个；弹一个补一个，每次 O(log K)、总 O(N log K)。
分治和堆怎么选？+
复杂度相同；分治不用额外堆、常数更小，堆实现更直观。
一条条顺序合并为什么慢？+
第 i 次要扫已合并的所有元素，退化到 O(NK)。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。