23. 合并 K 个升序链表（困难）

Blind 75 › 23. 合并 K 个升序链表（困难） （第 6 章）
文章工具

题目

给你 k 个单链表，每个链表都已经按升序排好。请把它们全部合并成一条升序链表，并返回新链表的头节点。

换句话说，就是做一次 k 路归并：每一轮从所有链表的“当前头部”里挑出最小的那个，接到结果尾部。

自造示例：lists = [[2,5,7],[1,3,4,4],[0,6]] → [0,1,2,3,4,4,5,6,7]

约束：链表数 0 ~ 104；每个链表长度 0 ~ 500；所有节点总数不超过 104；节点值 -104 ~ 104；每个链表已按升序排列。

思路

一句话：把 k 条有序链表的“当前头节点”放进一个最小堆，每次取堆顶接到结果尾部，再把它后面的节点补进堆。

最直白的做法：每取一个节点，就扫描 k 个链表的当前头，找出最小值。总共要取 n 个节点，每取一个扫 k 个 → 时间 O(n·k)。k 最大到 104，会太慢。

另一个“偷懒但能过”的做法：把所有节点值倒进数组，整体排序后再重建链表。时间 O(n log n)，确实能通过，但它丢掉了“每个链表本来就有序”这个重要信息，还额外用了 O(n) 空间存值。

关键观察：全局最小值一定藏在这 k 个“当前头”里——因为每条链表都是升序，如果某条链的头没被选中，它后面的节点只会更大，不可能抢先成为全局最小。所以候选节点永远只有 k 个。

于是问题就变成：在 k 个候选里反复“取最小值 + 补一个新候选”。这正是最小堆的标准用途：取出 O(log k)、插入 O(log k)，整体 O(n log k)。

解法

核心步骤：

  1. 建一个最小堆，把每条链表非空的头节点入堆（只入头，不入整条）。
  2. 用一个哨兵节点 dummy 让“头节点也是普通节点”统一处理。
  3. 循环：弹出堆顶，接到 tail；如果它后面还有节点，就把 next 入堆。
  4. 堆为空时结束，返回 dummy.next。

以 lists = [[2,5,7],[1,3,4,4],[0,6]] 为例，过程如下：

已取个数堆中候选（节点值）本次取出补入堆结果尾部
初始0,1,2———
10,1,2060
21,2,6130→1
32,3,6250→1→2
43,5,6340→1→2→3
54,5,6440→1→2→3→4
64,5,64—0→1→2→3→4→4
75,6570→1→2→3→4→4→5
86,76—0→1→2→3→4→4→5→6
977—0→1→2→3→4→4→5→6→7

堆里始终只保留“每条链下一个未取节点”，最多 k 个。

下图把上面 4 个步骤串成流程，并逐步演示：

23. 合并 K 个升序链表（困难） 解法步骤流程图
图① 解法步骤流程图（共 4 步）。
23. 合并 K 个升序链表（困难） 按步骤逐步执行的动画
动图② 按步骤依次推进（循环播放）。

C++

C++ 片段需补全 main() 函数才能运行在实训台打开 →
class 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* head : lists) {                 // 每条链只放一个头节点
 if (head != nullptr) {
 pq.push(head);
 }
 }  ListNode dummy(0);
 ListNode* tail = &dummy;
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。