合并 K 个升序链表
Merge k Sorted Lists
把 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.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i]按 升序 排列lists[i].length的总和不超过10^4
解题思路
小顶堆 · k 路归并
堆里只放每条链的当前头，谁最小谁出场
两条链合并时，只要比较两个头；k 条链合并，最直接的想法是每次在 k 个头里找最小。线性找是 O(k)，用堆可以降到 O(log k)。
先把每条非空链表的头节点放进小顶堆。每次弹出堆顶，接到结果链尾；如果这个节点还有后继，就把它的后继放回堆，代表这条链继续参赛。
三个头节点 2、1、3 入堆，堆顶是 1；堆里最多只有 k 个候选。
- k
- 3
堆里最多只有 k 个节点，不是把所有节点都塞进去。每弹出一个节点做一次 O(log k) 调整，总共 N 个节点，所以时间 O(N log k)，额外空间 O(k)。
自拟主例三条链长度相同，堆里的候选从 1、2、3 开始；取出 1 后立刻补入同链的 8，而不是一次把 L2 全部放入。
取出堆顶 10（来自 L2），追加到结果；这条链表已经取完。
- heap.size
- 1
最后要把结果链尾的 next 置空，否则尾节点可能还指向原链中的某个节点，形成多余连接。
易错点
- 把所有节点一次性入堆：时间退化为 O(N log N)，空间也变成 O(N)。
- 比较器写成 a->val < b->val：priority_queue 默认是大顶堆，会弹出最大值。
- 忘记 tail->next = nullptr：最后一个节点的 next 可能仍指向旧链，结果出现多余尾巴。
- 空链表也入堆：堆里出现空指针，取 val 时崩溃。
顺序两两合并
先合并前两条，再把结果与第三条合并……
实现最简单，但每次都要重新扫描已合并的长链，最坏 O(N·k)；仅作对照，不推荐在大 k 时使用。
复用第 21 题的 mergeTwo：先把 lists[0] 和 lists[1] 合并，再把结果与 lists[2] 合并，依次进行。
如果每条链长度相近，第 i 次合并要扫描的结果链长度约为 i·n，总比较次数是 n(1+2+…+k) = O(N·k)。k 很大时会明显变慢。
它的优点是代码极短、几乎不会写错，适合 k 很小或作为兜底方案。更好的改进是两两成对合并（分治），可以把时间降到 O(N log k)。
- 1结果先指向第一条链。
- 2依次与下一条链做二路合并。
- 3返回最终结果。
易错点
- lists 为空时直接访问 lists[0] 越界。
- 每次合并都新建节点：浪费空间，直接复用原节点即可。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
lists = [[2,7,9],[1,8,10],[3,4,11]]三条链表各自有序；堆为空，先把每个非空链表的头节点放进去。
空树 · null
查看 C++ 代码
延伸阅读
- k 路归并的“堆里只放当前头”是外部排序、日志合并等场景的常用模式。
- 两两成对合并（分治）不需要堆，也能做到 O(N log k)，适合不想手写比较器的场合。