23、合并K个升序链表
23、合并 K 个升序链表
题意
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
难度
困难
标签
排序、链表、堆
示例
输入：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
分析
合并 K 个升序链表，很容易就让我们想到之前做过的 021.合并两个有序链表，这道题是
升级版，合并 K 个。
021 题解的思路是通过比较两个链表的头节点，更小的那个就是新链表的头节点，再从剩
余的里面找到下一个节点。
021.%E5%90%88%E5%B9%B6%E4%B8%A4%E4%B8%AA%E6%9C%89%E5%BA%8F%E
9%93%BE%E8%A1%A8-20240202192400.png
那我们能不能用相同的方法来完成 K 个升序链表的合并呢？
第一个链表与第二个链表合并，然后新的链表再与第三个链表合并……，以此类推，看上
去能实现我们的目的。
但很遗憾，这样做的话，每一次合并后的新链表就会非常臃肿，并且在与第 K 个链表合
并时，之前链表的节点会多次被访问。
第一个链表被访问 k - 1 次，第二个链表被访问 k - 2 次……
看来不太行啊，我们需要另寻他路。
堆。
堆。
堆。
好了，我来告诉大家答案啦，我们可以把 k 个链表的节点都扔到堆中，然后就可以快速得
到最小的那个节点。堆顶的那个节点就是最小的。
023.%E5%90%88%E5%B9%B6K%E4%B8%AA%E5%8D%87%E5%BA%8F%E9%93%BE%
E8%A1%A8-20240204154331.png
每次把堆顶的那个节点取出来放到新的链表里，是不是瞬间一道难题就变成了一道简单题
呢？
先不着急看题解，我们来讲讲最小堆。
上图中的堆就叫最小堆，Min Heap，一种特殊的完全二叉树，满足以下性质：对于树中
的每个非叶子节点，节点的值都小于或等于其子节点的值。
这个特质确保了树的根节点总是所有节点中的最小值。
最小堆支持高效的数据插入和删除最小元素的操作，这使得它非常适合用来实现优先级队
列（Priority Queue）。
优先级队列允许按照一定的优先级顺序（如从小到大或从大到小）移除和添加数据。
• 插入操作：当插入一个新元素时，元素会被放在树的底部，然后，这个元素会和它的
父节点比较，如果新元素小于父节点，它们会交换位置。这个过程会一直持续，直到
新元素的父节点小于或等于新元素，或者新元素到达了根节点。
• 删除操作：删除最小元素通常意味着删除根节点。删除根节点后，通常会将最后一个
元素移动到根节点的位置，然后进行下沉操作（与子节点比较并与较小的子节点交
换），直到恢复最小堆的性质。
来具体模拟一下哈。
初始最小堆
假设我们有一个初始的最小堆，如下所示：
5
/
7 9
/
10 15
插入新元素
现在，我们尝试插入一个新元素 6 到这个最小堆中。
①插入：首先，我们将 6 放在树的底部，以保持完全二叉树的结构。完全二叉树要求除
了最后一层外，每一层都被完全填满，当插入一个新元素时，它总是被添加到这个完全二
叉树的最后一个位置，以保持树的完整性和平衡。
5
/
7 9
/
10 15 6
②、调整：由于 6 小于其父节点 9，我们需要调整堆，以恢复最小堆的性质。6 和 9 交换
位置。
5
/
7 6
/
10 15 9
现在，最小堆的性质恢复了，插入操作完成。
删除最小元素
接下来，我们尝试删除最小元素，即当前堆顶的 5。
①、删除：移除根节点 5，通常我们会将最后一个元素（这里是 9）移动到根节点的位
置。
9
/
7 6
/
10 15
②、调整：由于 9 大于其子节点 6 和 7，我们需要调整堆。9 应该与其最小的子节点 6 交
换位置，以恢复最小堆的性质。
6
/
7 9
/
10 15
现在，最小堆的性质再次恢复了，删除操作完成。
可以看到，刚好与我们的需求相符，我们可以通过最小堆来实现合并 K 个升序链表。
在 Java 中，优先级队列 PriorityQueue 就可以用来实现一个最小堆，我们通过重写
Comparator 接口中的 compare() 方法，定义出优先顺序，让 PriorityQueue 按照节点
（ListNode）的值（val）大小排序即可。
OK，我们先来看比较规则：
static Comparator<ListNode> cmp = new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
//重写 compare()方法，自定义 PriorityQueue 内部顺序
return Integer.compare(o1.val, o2.val);
}
};
然后我们就可以创建一个优先级队列 PriorityQueue 了：
PriorityQueue<ListNode> queue = new PriorityQueue<>(cmp);
也可以简化成：
PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> a.val - b.val);
通过 Lambda 表达式，可以更加简洁地定义比较规则。
接着，我们将链表的所有节点都放到优先级队列中：
for (ListNode list : lists) {
while (list != null) {
queue.add(list);
list = list.next;
}
}
然后，我们依次取出最小的节点，放到新的链表中：
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (!queue.isEmpty()) {
tail.next = queue.poll();
tail = tail.next;
}
最后，我们删除最后一个节点的 next 指针，然后返回新链表的头节点：
tail.next = null;
return dummy.next;
为什么要 tail.next = null; 呢？
在从优先级队列中取出节点并将其添加到新链表的尾部时，这个节点可能仍然保留着其在
原链表中的 next 指针。如果不将 tail.next 设置为 null，那么新链表的尾部可能会通过这
个未清除的 next 指针指向一个已经存在于新链表中的节点，从而创建一个循环引用。
我们来举一个没有 tail.next = null 的例子说明下：
-2 -> -1 -> -1 -> -1
-5 -> -3
假如第一个链表中的第二个节点 -1 出现在新链表的最后一个节点，那么新链表的最后一
个节点的 next 将指向第三个节点 -1，这样就会形成一个循环引用。
OK，来看完整的代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
*}
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
// 初始化优先级队列
PriorityQueue<ListNode> queue = new PriorityQueue<>((n1, n2) -> n1.val -
n2.val);
// 将所有链表的所有节点都添加到优先级队列中
for (ListNode list : lists) {
while (list != null) {
queue.add(list);
list = list.next;
}
}
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
// 从优先级队列中依次取出节点，构建新的链表
while (!queue.isEmpty()) {
tail.next = queue.poll(); // 连接新节点
tail = tail.next; // 移动尾指针
}
tail.next = null; // 防止老的 next 指针影响新链表的结构
return dummy.next;
}
}
OK，我们来看一下题解效率：
023.%E5%90%88%E5%B9%B6K%E4%B8%AA%E5%8D%87%E5%BA%8F%E9%93%BE%
E8%A1%A8-20240204200524.png
分析 2
只击败了 39% 的用户，看来我们的题解效率还可以继续提高。那怎么提高呢？
在前面的题解里，我们一次性将所有的链表节点都加入到了优先级队列中，这样就增加了
优先级队列的维护成本。
• 时间复杂度：O(N log N)，其中 N 是所有链表中节点的总数。每次向优先级队列中加
入或取出节点时，都需要 O(log N) 的时间进行堆调整。由于二叉堆是完全二叉树，
其高度 h 与节点数量 n 之间的关系是 h = O(log n)。具体来说，对于含有 n 个节点的
完全二叉树，其高度大约是 log2(n)。这是因为，每增加一层，节点数量大约翻一
倍。
• 空间复杂度：O(N)，因为需要将所有节点都存储在优先级队列中。
在这种方法中，由于一次性将所有节点都加入到优先级队列中，队列的大小会达到 N，这
导致了每次插入和删除操作都需要在一个较大的堆上进行，增加了堆调整的成本。
好，我们来看下面这张图。
023.%E5%90%88%E5%B9%B6K%E4%B8%AA%E5%8D%87%E5%BA%8F%E9%93%BE%
E8%A1%A8-20240204202427.png
可以看到，我们只需要将 K 个链表的头节点加入到优先级队列中，也能得到一个最小
堆，然后我们就可以通过优先级队列的特性，快速得到最小的节点。
之后再把最小的节点取出来，把它的 next 节点加入到优先级队列中，如此循环，直到优
先级队列为空。
这样，我们就只需要维护一个 K 大小的优先级队列，而不是 N 大小的优先级队列。
• 时间复杂度：O(N log K)，其中 N 是所有链表中节点的总数，K 是链表的数量。每次
向优先级队列中加入或取出节点时，都需要 O(log K) 的时间进行堆调整。
• 空间复杂度：O(K)，因为队列中最多同时只有 K 个元素，即每个链表的当前头节
点。
在这种方法中，优先级队列的大小被限制为 K，这意味着堆调整的成本相比于之前的方法
大大减少了。
定义一个优先级队列：
PriorityQueue<ListNode> queue = new PriorityQueue<>((n1, n2) -> n1.val -
n2.val);
然后将 K 个链表的头节点加入到优先级队列中：
for (ListNode list : lists) {
if (list != null) {
queue.add(list);
}
}
接着，我们依次取出最小的节点，放到新的链表中：
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (!queue.isEmpty()) {
ListNode minNode = queue.poll();
tail.next = minNode;
tail = tail.next;
if (minNode.next != null) {
queue.add(minNode.next);
}
}
最后，我们删除最后一个节点的 next 指针，然后返回新链表的头节点：
tail.next = null;
return dummy.next;
OK，我们来看完整的代码：
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
// 初始化优先级队列
PriorityQueue<ListNode> queue = new PriorityQueue<>((n1, n2) -> n1.val -
n2.val);
// 将 K 个链表的头节点加入到优先级队列中
for (ListNode list : lists) {
if (list != null) {
queue.add(list);
}
}
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
// 从优先级队列中依次取出节点，构建新的链表
while (!queue.isEmpty()) {
ListNode minNode = queue.poll();
tail.next = minNode; // 连接新节点
tail = tail.next; // 移动尾指针
if (minNode.next != null) {
queue.add(minNode.next); // 将下一个节点加入到优先级队列中
}
}
tail.next = null; // 防止老的 next 指针影响新链表的结构
return dummy.next;
}
}
来看题解的效率：
023.%E5%90%88%E5%B9%B6K%E4%B8%AA%E5%8D%87%E5%BA%8F%E9%93%BE%
E8%A1%A8-20240204203826.png
果然提升了不少。
总结
这道题我们通过优先级队列 PriorityQueue 来实现了合并 K 个升序链表，涉及到了我们
之前未曾接触过的数据结构——堆。
最小堆是一种特殊的完全二叉树，满足以下性质：对于树中的每个非叶子节点，节点的值
都小于或等于其子节点的值。
记住这个特质。
这样子就能够把最小的元素放在根节点上，$ O(1) $ 的时间复杂度就得到了最小的元素。
怎么实现在$ O() $的时间内插入一个新元素呢？
要维持 完全二叉树 的特质，就只能在最底层的最右边的叶子节点的右边插入，如果最底
层满了，那么就新建一层，再放到这一层中的最左边即可。
那么第二步就是要维护 “每个节点的值都大于等于父节点的值” 这个特质。如果插入的这
个节点的值小于它的父节点，那么它就向上调整，跟它的父节点直接交换，一直 向上调
整 ，直到它不小于父节点或者抵达了根节点，如下：
023.%E5%90%88%E5%B9%B6K%E4%B8%AA%E5%8D%87%E5%BA%8F%E9%93%BE%
E8%A1%A8-20240204205030.png
如何删除呢？
我们显然不能直接删掉根节点，那样就变成了两个最小堆（小根堆）。
一般会把根节点与最后一个节点交换，然后删除。如果当前的结构不满足最小堆的特质，
需要 向下调整 ，与子节点中比较小的一个交换位置，直到恢复最小堆。因为树高最多$
， 所 以 我 们 最 多 就 调 整 $次。
回顾一下这道题所涉及到的 Java 基础知识：
• 优先级队列 PriorityQueue
• Lambda 表达式
• Comparator 接口
• 时间复杂度
• 链表 LinkedList
力扣链接：https://leetcode.cn/problems/merge-k-sorted-lists/
