23. 合并 K 个升序链表

题目描述

给 K 条升序链表，把它们合并成一条升序链表返回。

思路解析

把全部节点倒进数组排一遍能做，但完全没利用「每条本来就有序」这个大便宜——重排是 O(N log N)，还白白丢掉了有序信息。

转折：把 K 条捉对合并——合并两条有序链表我们是会的(比头节点，谁小接谁)。两两合完再两两合，像淘汰赛，log k 轮就汇成一条。每个节点每轮只被碰一次，所以是 O(N log k)，比重排更快。

合并 A、B · 起步：先合并 A、B。p1 指 A 头 1，p2 指 B 头 1，结果链表(下方)还空着(虚线占位)。挂个 dummy 哨兵当结果起点，开始比头。

1(A) ≤ 1(B) · 取 A 的 1：两个头都是 1，1 ≤ 1 取 A 的 1(一样大先接谁都行)接进结果，p1 前进到 4。结果链表长出第一个 1，tail 指向它。

4(A) > 1(B) · 取 B 的 1：现在比 A 的 4 和 B 的 1：4 大于 1，取 B 的 1，p2 前进到 3。结果：1 → 1。

4(A) > 3(B) · 取 B 的 3：A 的 4 仍比 B 的 3 大：4 大于 3，取 B 的 3，p2 前进到 4。结果：1 → 1 → 3。谁小接谁，指针各自往后爬。

4(A) ≤ 4(B) · 取 A 的 4：这回 A、B 头都是 4：4 ≤ 4 取 A 的 4，p1 前进到 5。结果：1 → 1 → 3 → 4。

5(A) > 4(B) · 取 B 的 4 · B 用完：比 A 的 5 和 B 的 4：5 大于 4，取 B 的 4，p2 走到头——B 用完了。结果：1 → 1 → 3 → 4 → 4。

负例 · B 空了 · A 剩段整条接上：关键负例：一条先走空(B 空)，就不必再逐个比了——把另一条剩下的整段(A 的 5)直接接到结果尾巴。结果：1 → 1 → 3 → 4 → 4 → 5。

A+B 合并完成 · 再与 C 合：A、B 合成了 1→1→3→4→4→5。这就是「合并两条」的一整轮。下一轮拿这个结果再和 C=[2→6] 合并，还是同一套：比头、接小的，最终汇成 1→1→2→3→4→4→5→6。

面对「合并 K 个」别慌：把它拆成你已经会的「合并两个」，再用分治两两推进。或者用小顶堆同时盯住 K 个头，每次弹最小，也是 O(N log k)。

参考代码（Python）

1def mergeKLists(self, lists):
2    if not lists: return None
3    while len(lists) > 1:                   # 两两合并，直到剩一条
4        merged = []
5        for i in range(0, len(lists), 2):
6            a = lists[i]
7            b = lists[i + 1] if i + 1 < len(lists) else None  # 落单条配 None
8            merged.append(self.mergeTwo(a, b))   # 复用合并两条
9        lists = merged
10    return lists[0]
11
12def mergeTwo(self, a, b):                   # 就是 LC21
13    dummy = tail = ListNode()
14    while a and b:
15        if a.val <= b.val: tail.next, a = a, a.next   # 谁小接谁
16        else: tail.next, b = b, b.next
17        tail = tail.next
18    tail.next = a or b                      # 剩段整条接上
19    return dummy.next

复杂度分析

• 时间复杂度：O(N log k) —— N 个节点总数，每轮全碰一次、共 log k 轮
• 空间复杂度：O(1) —— 原地接指针，不新建节点(不计递归栈)

套路模板

堆解法：把 K 个头扔进小顶堆，每次弹最小、接走，再把它的后继补进堆。堆顶永远是当前全局最小，同样 O(N log k)。

1import heapq
2h = [(node.val, i, node) for i, node in enumerate(lists) if node]
3heapq.heapify(h)                 # K 个头进堆
4dummy = cur = ListNode()
5while h:
6    val, i, node = heapq.heappop(h)   # 弹出当前全局最小头
7    cur.next = node; cur = node
8    if node.next: heapq.heappush(h, (node.next.val, i, node.next))
9return dummy.next

易错点

• 错误写法：把所有节点收集再排序 O(N log N)，或逐条挨个合 O(Nk) → 正确写法：两两合并 / 小顶堆，O(N log k)（重排丢了「已有序」信息、逐条合让早期节点被反复扫；分治或堆才把 k 压成 log k）
• 错误写法：堆里只放 (val, node) → 正确写法：放 (val, i, node)，加个序号 i（val 相等时 Python 会去比 node 对象、报 TypeError；塞个唯一序号当第二关键字打破平局）
• 错误写法：两两合并漏掉落单的那条 → 正确写法：i+1 越界时 b 取 None（K 为奇数时最后一条没配对，要让它和 None 合并(即原样保留)）

以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。