题目描述
给 K 条升序链表，把它们合并成一条升序链表返回。
链表 = [1→4→5] [1→3→4] [2→6]
输出 = 1→1→2→3→4→4→5→6
思路解析
把全部节点倒进数组排一遍能做，但完全没利用「每条本来就有序」这个大便宜，太亏。
把 K 条捉对合并：合并两条有序链表是会的（比头节点，小的接走）。两两合完再两两合，像比赛淘汰，log k 轮搞定。
合并两条有序链表的核心动作：拿两个当前头比一下，小的那个接到结果后面、指针往后挪一格，反复直到一条走完。
先合并 A 和 B：先拿 A、B 两条来合并。两个头都是 1，挑 A 的 1 先接走（一样大先接谁都行）。
接走 A 的 1：A 的 1 接进结果（标绿），a 挪到下一个 4。现在比 A 的 4 和 B 的 1，B 的 1 更小。
接走 B 的 1、3：B 的 1 比 A 的 4 小，接走；B 的 3 还是比 4 小，也接走。就这样谁小接谁，指针各自往后爬。
A、B 合并完成：一路接到底，A 和 B 合成了 1→1→3→4→4→5。一条搞定，还剩链表 C 没合。
再与 C 合并：把刚才的结果再和 C=[2→6] 合并，还是同一套：比头、接小的。
全部合并完成：最终合成 1→1→2→3→4→4→5→6。K 条链表通过一轮轮两两合并，汇成了一条。
面对「合并 K 个」别慌：把它拆成你已经会的「合并两个」，再用分治两两推进。或者用小顶堆同时盯住 K 个头，每次弹最小。
参考代码（Python）
Python
1def mergeKLists(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
8 merged.append(mergeTwo(a, b)) # 复用合并两条
9 lists = merged
10 return lists[0]复杂度分析
- 时间复杂度：O(N log k) —— N 个节点，log k 轮
- 空间复杂度：O(1) —— 原地接指针（不计递归）
套路模板
堆解法：把 K 个头扔进小顶堆，每次弹最小、接走，再把它的后继补进堆。堆顶永远是当前全局最小。
Python
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易错点
- ❌ 堆里只放 (val, node) → ✅ 放 (val, i, node)，加个序号（val 相等时 Python 会去比 node 对象，报错；塞个唯一序号 i 当第二关键字打破平局）
- ❌ 两两合并时漏掉落单的那条 → ✅ i+1 越界时 b 取 None（K 为奇数时最后一条没有配对，要让它和 None 合并（即原样保留））
- ❌ 把所有节点收集再排序 → ✅ 利用已有序，比头接小的（重排是 O(N log N) 还丢了有序信息，合并法才是 O(N log k)）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。