023.合并 K 个升序链表

作者：沉默王二
发布时间：2024-02-05T08:11:04.738+0800

鲁迅说过，今天立春了，再刷一道 LeetCode 题解，迎接春天的脚步，虽然天空还飘着雪花，但我内心已经感受到了春天的气息，以及二哥的 LeetCode 题解的温暖。

技术派阅读地址：https://paicoding.com/column/7/23

语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
这道题可以说完全重写了，给出 2 道大家完全都能掌握的题解（最小堆和优先级队列）。
增加代码注释，这样大家更容易看懂并掌握题解；
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
增加手绘图，这样大家更容易理解解题思路；
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

题意

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

难度

困难

示例

输入：lists = [[1,4,5],[1,3,4],[2,6]]

解释：链表数组如下：[ 1->4->5, 1->3->4, 2->6]将它们合并到一个有序链表中得到。1->1->2->3->4->4->5->6

分析

合并 K 个升序链表，很容易就让我们想到之前做过的 021.合并两个有序链表 ，这道题是升级版，合并 K 个。

021 题解的思路是通过比较两个链表的头节点，更小的那个就是新链表的头节点，再从剩余的里面找到下一个节点。

那我们能不能用相同的方法来完成 K 个升序链表的合并呢？

第一个链表与第二个链表合并，然后新的链表再与第三个链表合并……，以此类推，看上去能实现我们的目的。

但很遗憾，这样做的话，每一次合并后的新链表就会非常臃肿，并且在与第 K 个链表合并时，之前链表的节点会多次被访问。

第一个链表被访问k - 1次，第二个链表被访问k - 2次……

看来不太行啊，我们需要另寻他路。

堆。

好了，我来告诉大家答案啦，我们可以把 k 个链表的节点都扔到堆中，然后就可以快速得到最小的那个节点。堆顶的那个节点就是最小的。

每次把堆顶的那个节点取出来放到新的链表里，是不是瞬间一道难题就变成了一道简单题呢？

先不着急看题解，我们来讲讲最小堆。

上图中的堆就叫最小堆，Min Heap，一种特殊的完全二叉树，满足以下性质：对于树中的每个非叶子节点，节点的值都小于或等于其子节点的值。

这个特质确保了树的根节点总是所有节点中的最小值。

最小堆支持高效的数据插入和删除最小元素的操作，这使得它非常适合用来实现优先级队列（Priority Queue）。

优先级队列允许按照一定的优先级顺序（如从小到大或从大到小）移除和添加数据。

插入操作：当插入一个新元素时，元素会被放在树的底部，然后，这个元素会和它的父节点比较，如果新元素小于父节点，它们会交换位置。这个过程会一直持续，直到新元素的父节点小于或等于新元素，或者新元素到达了根节点。
删除操作：删除最小元素通常意味着删除根节点。删除根节点后，通常会将最后一个元素移动到根节点的位置，然后进行下沉操作（与子节点比较并与较小的子节点交换），直到恢复最小堆的性质。

来具体模拟一下哈。

初始最小堆

假设我们有一个初始的最小堆，如下所示：

 7   9    / \   10  15

插入新元素

现在，我们尝试插入一个新元素 6 到这个最小堆中。

①插入：首先，我们将 6 放在树的底部，以保持完全二叉树的结构。完全二叉树要求除了最后一层外，每一层都被完全填满，当插入一个新元素时，它总是被添加到这个完全二叉树的最后一个位置，以保持树的完整性和平衡。

 7    9    / \    \    10 15    6

②、调整：由于 6 小于其父节点 9，我们需要调整堆，以恢复最小堆的性质。6 和 9 交换位置。

 7     6    / \     \   10 15     9

现在，最小堆的性质恢复了，插入操作完成。

删除最小元素

接下来，我们尝试删除最小元素，即当前堆顶的 5。

①、删除：移除根节点 5，通常我们会将最后一个元素（这里是 9）移动到根节点的位置。

 7   6    / \   10  15

②、调整：由于 9 大于其子节点 6 和 7，我们需要调整堆。9 应该与其最小的子节点 6 交换位置，以恢复最小堆的性质。

 7   9    / \   10  15

现在，最小堆的性质再次恢复了，删除操作完成。

可以看到，刚好与我们的需求相符，我们可以通过最小堆来实现合并 K 个升序链表。

在 Java 中，优先级队列 PriorityQueue 就可以用来实现一个最小堆，我们通过重写 Comparator 接口中的 compare() 方法，定义出优先顺序，让 PriorityQueue 按照节点（ListNode）的值（val）大小排序即可。

OK，我们先来看比较规则：

static Comparator cmp = new Comparator() {

public int compare(ListNode o1, ListNode o2) {        //重写compare()方法，自定义PriorityQueue内部顺序        return Integer.compare(o1.val, o2.val);    }};

然后我们就可以创建一个优先级队列 PriorityQueue 了：

PriorityQueue queue = new PriorityQueue<>(cmp);

也可以简化成：

PriorityQueue queue = new PriorityQueue<>((a, b) -> a.val - b.val);

通过 Lambda 表达式 ，可以更加简洁地定义比较规则。

接着，我们将链表的所有节点都放到优先级队列中：

for (ListNode list : lists) {

    queue.add(list);        list = list.next;    }}

然后，我们依次取出最小的节点，放到新的链表中：

ListNode dummy = new ListNode(0);

while (!queue.isEmpty()) { tail.next = queue.poll(); tail = tail.next;}

最后，我们删除最后一个节点的 next 指针，然后返回新链表的头节点：

tail.next = null;

为什么要 tail.next = null; 呢？

在从优先级队列中取出节点并将其添加到新链表的尾部时，这个节点可能仍然保留着其在原链表中的 next 指针。如果不将 tail.next 设置为 null，那么新链表的尾部可能会通过这个未清除的 next 指针指向一个已经存在于新链表中的节点，从而创建一个循环引用。

我们来举一个没有 tail.next = null 的例子说明下：

-2->-1->-1->-1

假如第一个链表中的第二个节点 -1 出现在新链表的最后一个节点，那么新链表的最后一个节点的 next 将指向第三个节点 -1，这样就会形成一个循环引用。

OK，来看完整的代码：

/**

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 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，我们来看一下题解效率：

分析 2

只击败了 39% 的用户，看来我们的题解效率还可以继续提高。那怎么提高呢？

在前面的题解里，我们一次性将所有的链表节点都加入到了优先级队列中，这样就增加了优先级队列的维护成本。

时间复杂度：O(N log N)，其中 N 是所有链表中节点的总数。每次向优先级队列中加入或取出节点时，都需要 O(log N) 的时间进行堆调整。由于二叉堆是完全二叉树，其高度 h 与节点数量 n 之间的关系是 h = O(log n)。具体来说，对于含有 n 个节点的完全二叉树，其高度大约是 log2(n)。这是因为，每增加一层，节点数量大约翻一倍。
空间复杂度：O(N)，因为需要将所有节点都存储在优先级队列中。

在这种方法中，由于一次性将所有节点都加入到优先级队列中，队列的大小会达到 N，这导致了每次插入和删除操作都需要在一个较大的堆上进行，增加了堆调整的成本。

好，我们来看下面这张图。

可以看到，我们只需要将 K 个链表的头节点加入到优先级队列中，也能得到一个最小堆，然后我们就可以通过优先级队列的特性，快速得到最小的节点。

之后再把最小的节点取出来，把它的 next 节点加入到优先级队列中，如此循环，直到优先级队列为空。

这样，我们就只需要维护一个 K 大小的优先级队列，而不是 N 大小的优先级队列。

时间复杂度：O(N log K)，其中 N 是所有链表中节点的总数，K 是链表的数量。每次向优先级队列中加入或取出节点时，都需要 O(log K) 的时间进行堆调整。
空间复杂度：O(K)，因为队列中最多同时只有 K 个元素，即每个链表的当前头节点。

在这种方法中，优先级队列的大小被限制为 K，这意味着堆调整的成本相比于之前的方法大大减少了。

定义一个优先级队列：

PriorityQueue queue = new PriorityQueue<>((n1, n2) -> n1.val - n2.val);

然后将 K 个链表的头节点加入到优先级队列中：

for (ListNode list : lists) {

    queue.add(list);    }}

接着，我们依次取出最小的节点，放到新的链表中：

ListNode dummy = new ListNode(0);

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;

OK，我们来看完整的代码：

class Solution {

    // 初始化优先级队列        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;    }}

来看题解的效率：

果然提升了不少。

总结

这道题我们通过**优先级队列 ** PriorityQueue 来实现了合并 K 个升序链表，涉及到了我们之前未曾接触过的数据结构——堆。

最小堆是一种特殊的完全二叉树，满足以下性质：对于树中的每个非叶子节点，节点的值都小于或等于其子节点的值。

记住这个特质。

这样子就能够把最小的元素放在根节点上，的**时间复杂度 **就得到了最小的元素。

怎么实现在的时间内插入一个新元素呢？

要维持 完全二叉树 的特质，就只能在最底层的最右边的叶子节点的右边插入，如果最底层满了，那么就新建一层，再放到这一层中的最左边即可。

那么第二步就是要维护 “每个节点的值都大于等于父节点的值” 这个特质。如果插入的这个节点的值小于它的父节点，那么它就向上调整，跟它的父节点直接交换，一直 向上调整 ，直到它不小于父节点或者抵达了根节点，如下：

如何删除呢？

我们显然不能直接删掉根节点，那样就变成了两个最小堆（小根堆）。

一般会把根节点与最后一个节点交换，然后删除。如果当前的结构不满足最小堆的特质，需要 向下调整 ，与子节点中比较小的一个交换位置，直到恢复最小堆。因为树高最多，所以我们最多就调整次。

回顾一下这道题所涉及到的 Java 基础知识：

力扣链接：https://leetcode.cn/problems/merge-k-sorted-lists/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4300+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

技术派阅读地址：https://paicoding.com/column/7/23

语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
这道题可以说完全重写了，给出 2 道大家完全都能掌握的题解（最小堆和优先级队列）。
增加代码注释，这样大家更容易看懂并掌握题解；
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
增加手绘图，这样大家更容易理解解题思路；
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

题意

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

难度

困难

示例

输入：lists = [[1,4,5],[1,3,4],[2,6]]

解释：链表数组如下：[ 1->4->5, 1->3->4, 2->6]将它们合并到一个有序链表中得到。1->1->2->3->4->4->5->6

分析

合并 K 个升序链表，很容易就让我们想到之前做过的 021.合并两个有序链表 ，这道题是升级版，合并 K 个。

021 题解的思路是通过比较两个链表的头节点，更小的那个就是新链表的头节点，再从剩余的里面找到下一个节点。

那我们能不能用相同的方法来完成 K 个升序链表的合并呢？

第一个链表与第二个链表合并，然后新的链表再与第三个链表合并……，以此类推，看上去能实现我们的目的。

但很遗憾，这样做的话，每一次合并后的新链表就会非常臃肿，并且在与第 K 个链表合并时，之前链表的节点会多次被访问。

第一个链表被访问k - 1次，第二个链表被访问k - 2次……

看来不太行啊，我们需要另寻他路。

堆。

好了，我来告诉大家答案啦，我们可以把 k 个链表的节点都扔到堆中，然后就可以快速得到最小的那个节点。堆顶的那个节点就是最小的。

每次把堆顶的那个节点取出来放到新的链表里，是不是瞬间一道难题就变成了一道简单题呢？

先不着急看题解，我们来讲讲最小堆。

上图中的堆就叫最小堆，Min Heap，一种特殊的完全二叉树，满足以下性质：对于树中的每个非叶子节点，节点的值都小于或等于其子节点的值。

这个特质确保了树的根节点总是所有节点中的最小值。

最小堆支持高效的数据插入和删除最小元素的操作，这使得它非常适合用来实现优先级队列（Priority Queue）。

优先级队列允许按照一定的优先级顺序（如从小到大或从大到小）移除和添加数据。

插入操作：当插入一个新元素时，元素会被放在树的底部，然后，这个元素会和它的父节点比较，如果新元素小于父节点，它们会交换位置。这个过程会一直持续，直到新元素的父节点小于或等于新元素，或者新元素到达了根节点。
删除操作：删除最小元素通常意味着删除根节点。删除根节点后，通常会将最后一个元素移动到根节点的位置，然后进行下沉操作（与子节点比较并与较小的子节点交换），直到恢复最小堆的性质。

来具体模拟一下哈。

初始最小堆

假设我们有一个初始的最小堆，如下所示：

 7   9    / \   10  15

插入新元素

现在，我们尝试插入一个新元素 6 到这个最小堆中。

 7    9    / \    \    10 15    6

②、调整：由于 6 小于其父节点 9，我们需要调整堆，以恢复最小堆的性质。6 和 9 交换位置。

 7     6    / \     \   10 15     9

现在，最小堆的性质恢复了，插入操作完成。

删除最小元素

接下来，我们尝试删除最小元素，即当前堆顶的 5。

①、删除：移除根节点 5，通常我们会将最后一个元素（这里是 9）移动到根节点的位置。

 7   6    / \   10  15

②、调整：由于 9 大于其子节点 6 和 7，我们需要调整堆。9 应该与其最小的子节点 6 交换位置，以恢复最小堆的性质。

 7   9    / \   10  15

现在，最小堆的性质再次恢复了，删除操作完成。

可以看到，刚好与我们的需求相符，我们可以通过最小堆来实现合并 K 个升序链表。

OK，我们先来看比较规则：

static Comparator cmp = new Comparator() {

public int compare(ListNode o1, ListNode o2) {        //重写compare()方法，自定义PriorityQueue内部顺序        return Integer.compare(o1.val, o2.val);    }};

然后我们就可以创建一个优先级队列 PriorityQueue 了：

PriorityQueue queue = new PriorityQueue<>(cmp);

也可以简化成：

PriorityQueue queue = new PriorityQueue<>((a, b) -> a.val - b.val);

通过 Lambda 表达式 ，可以更加简洁地定义比较规则。

接着，我们将链表的所有节点都放到优先级队列中：

for (ListNode list : lists) {

    queue.add(list);        list = list.next;    }}

然后，我们依次取出最小的节点，放到新的链表中：

ListNode dummy = new ListNode(0);

while (!queue.isEmpty()) { tail.next = queue.poll(); tail = tail.next;}

最后，我们删除最后一个节点的 next 指针，然后返回新链表的头节点：

tail.next = null;

为什么要 tail.next = null; 呢？

我们来举一个没有 tail.next = null 的例子说明下：

-2->-1->-1->-1

OK，来看完整的代码：

/**

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 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，我们来看一下题解效率：

分析 2

只击败了 39% 的用户，看来我们的题解效率还可以继续提高。那怎么提高呢？

在前面的题解里，我们一次性将所有的链表节点都加入到了优先级队列中，这样就增加了优先级队列的维护成本。

时间复杂度：O(N log N)，其中 N 是所有链表中节点的总数。每次向优先级队列中加入或取出节点时，都需要 O(log N) 的时间进行堆调整。由于二叉堆是完全二叉树，其高度 h 与节点数量 n 之间的关系是 h = O(log n)。具体来说，对于含有 n 个节点的完全二叉树，其高度大约是 log2(n)。这是因为，每增加一层，节点数量大约翻一倍。
空间复杂度：O(N)，因为需要将所有节点都存储在优先级队列中。

好，我们来看下面这张图。

之后再把最小的节点取出来，把它的 next 节点加入到优先级队列中，如此循环，直到优先级队列为空。

这样，我们就只需要维护一个 K 大小的优先级队列，而不是 N 大小的优先级队列。

时间复杂度：O(N log K)，其中 N 是所有链表中节点的总数，K 是链表的数量。每次向优先级队列中加入或取出节点时，都需要 O(log K) 的时间进行堆调整。
空间复杂度：O(K)，因为队列中最多同时只有 K 个元素，即每个链表的当前头节点。

在这种方法中，优先级队列的大小被限制为 K，这意味着堆调整的成本相比于之前的方法大大减少了。

定义一个优先级队列：

PriorityQueue queue = new PriorityQueue<>((n1, n2) -> n1.val - n2.val);

然后将 K 个链表的头节点加入到优先级队列中：

for (ListNode list : lists) {

    queue.add(list);    }}

接着，我们依次取出最小的节点，放到新的链表中：

ListNode dummy = new ListNode(0);

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;

OK，我们来看完整的代码：

class Solution {

    // 初始化优先级队列        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;    }}

来看题解的效率：

果然提升了不少。

总结

这道题我们通过**优先级队列 ** PriorityQueue 来实现了合并 K 个升序链表，涉及到了我们之前未曾接触过的数据结构——堆。

最小堆是一种特殊的完全二叉树，满足以下性质：对于树中的每个非叶子节点，节点的值都小于或等于其子节点的值。

记住这个特质。

这样子就能够把最小的元素放在根节点上，的**时间复杂度 **就得到了最小的元素。

怎么实现在的时间内插入一个新元素呢？

要维持 完全二叉树 的特质，就只能在最底层的最右边的叶子节点的右边插入，如果最底层满了，那么就新建一层，再放到这一层中的最左边即可。

如何删除呢？

我们显然不能直接删掉根节点，那样就变成了两个最小堆（小根堆）。

回顾一下这道题所涉及到的 Java 基础知识：

力扣链接：https://leetcode.cn/problems/merge-k-sorted-lists/

一步一个脚印

（优惠券仅 300 张，数量有限）

技术派阅读地址：https://paicoding.com/column/7/23

语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
这道题可以说完全重写了，给出 2 道大家完全都能掌握的题解（最小堆和优先级队列）。
增加代码注释，这样大家更容易看懂并掌握题解；
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
增加手绘图，这样大家更容易理解解题思路；
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

题意

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

难度

困难

示例

输入：lists = [[1,4,5],[1,3,4],[2,6]]

解释：链表数组如下：[ 1->4->5, 1->3->4, 2->6]将它们合并到一个有序链表中得到。1->1->2->3->4->4->5->6

分析

合并 K 个升序链表，很容易就让我们想到之前做过的 021.合并两个有序链表 ，这道题是升级版，合并 K 个。

021 题解的思路是通过比较两个链表的头节点，更小的那个就是新链表的头节点，再从剩余的里面找到下一个节点。

那我们能不能用相同的方法来完成 K 个升序链表的合并呢？

第一个链表与第二个链表合并，然后新的链表再与第三个链表合并……，以此类推，看上去能实现我们的目的。

但很遗憾，这样做的话，每一次合并后的新链表就会非常臃肿，并且在与第 K 个链表合并时，之前链表的节点会多次被访问。

第一个链表被访问k - 1次，第二个链表被访问k - 2次……

看来不太行啊，我们需要另寻他路。

堆。

好了，我来告诉大家答案啦，我们可以把 k 个链表的节点都扔到堆中，然后就可以快速得到最小的那个节点。堆顶的那个节点就是最小的。

每次把堆顶的那个节点取出来放到新的链表里，是不是瞬间一道难题就变成了一道简单题呢？

先不着急看题解，我们来讲讲最小堆。

上图中的堆就叫最小堆，Min Heap，一种特殊的完全二叉树，满足以下性质：对于树中的每个非叶子节点，节点的值都小于或等于其子节点的值。

这个特质确保了树的根节点总是所有节点中的最小值。

最小堆支持高效的数据插入和删除最小元素的操作，这使得它非常适合用来实现优先级队列（Priority Queue）。

优先级队列允许按照一定的优先级顺序（如从小到大或从大到小）移除和添加数据。

插入操作：当插入一个新元素时，元素会被放在树的底部，然后，这个元素会和它的父节点比较，如果新元素小于父节点，它们会交换位置。这个过程会一直持续，直到新元素的父节点小于或等于新元素，或者新元素到达了根节点。
删除操作：删除最小元素通常意味着删除根节点。删除根节点后，通常会将最后一个元素移动到根节点的位置，然后进行下沉操作（与子节点比较并与较小的子节点交换），直到恢复最小堆的性质。

来具体模拟一下哈。

初始最小堆

假设我们有一个初始的最小堆，如下所示：

 7   9    / \   10  15

插入新元素

现在，我们尝试插入一个新元素 6 到这个最小堆中。

 7    9    / \    \    10 15    6

②、调整：由于 6 小于其父节点 9，我们需要调整堆，以恢复最小堆的性质。6 和 9 交换位置。

 7     6    / \     \   10 15     9

现在，最小堆的性质恢复了，插入操作完成。

删除最小元素

接下来，我们尝试删除最小元素，即当前堆顶的 5。

①、删除：移除根节点 5，通常我们会将最后一个元素（这里是 9）移动到根节点的位置。

 7   6    / \   10  15

②、调整：由于 9 大于其子节点 6 和 7，我们需要调整堆。9 应该与其最小的子节点 6 交换位置，以恢复最小堆的性质。

 7   9    / \   10  15

现在，最小堆的性质再次恢复了，删除操作完成。

可以看到，刚好与我们的需求相符，我们可以通过最小堆来实现合并 K 个升序链表。

OK，我们先来看比较规则：

static Comparator cmp = new Comparator() {

public int compare(ListNode o1, ListNode o2) {        //重写compare()方法，自定义PriorityQueue内部顺序        return Integer.compare(o1.val, o2.val);    }};

然后我们就可以创建一个优先级队列 PriorityQueue 了：

PriorityQueue queue = new PriorityQueue<>(cmp);

也可以简化成：

PriorityQueue queue = new PriorityQueue<>((a, b) -> a.val - b.val);

通过 Lambda 表达式 ，可以更加简洁地定义比较规则。

接着，我们将链表的所有节点都放到优先级队列中：

for (ListNode list : lists) {

    queue.add(list);        list = list.next;    }}

然后，我们依次取出最小的节点，放到新的链表中：

ListNode dummy = new ListNode(0);

while (!queue.isEmpty()) { tail.next = queue.poll(); tail = tail.next;}

最后，我们删除最后一个节点的 next 指针，然后返回新链表的头节点：

tail.next = null;

为什么要 tail.next = null; 呢？

我们来举一个没有 tail.next = null 的例子说明下：

-2->-1->-1->-1

OK，来看完整的代码：

/**

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 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，我们来看一下题解效率：

分析 2

只击败了 39% 的用户，看来我们的题解效率还可以继续提高。那怎么提高呢？

在前面的题解里，我们一次性将所有的链表节点都加入到了优先级队列中，这样就增加了优先级队列的维护成本。

时间复杂度：O(N log N)，其中 N 是所有链表中节点的总数。每次向优先级队列中加入或取出节点时，都需要 O(log N) 的时间进行堆调整。由于二叉堆是完全二叉树，其高度 h 与节点数量 n 之间的关系是 h = O(log n)。具体来说，对于含有 n 个节点的完全二叉树，其高度大约是 log2(n)。这是因为，每增加一层，节点数量大约翻一倍。
空间复杂度：O(N)，因为需要将所有节点都存储在优先级队列中。

好，我们来看下面这张图。

之后再把最小的节点取出来，把它的 next 节点加入到优先级队列中，如此循环，直到优先级队列为空。

这样，我们就只需要维护一个 K 大小的优先级队列，而不是 N 大小的优先级队列。

时间复杂度：O(N log K)，其中 N 是所有链表中节点的总数，K 是链表的数量。每次向优先级队列中加入或取出节点时，都需要 O(log K) 的时间进行堆调整。
空间复杂度：O(K)，因为队列中最多同时只有 K 个元素，即每个链表的当前头节点。

在这种方法中，优先级队列的大小被限制为 K，这意味着堆调整的成本相比于之前的方法大大减少了。

定义一个优先级队列：

PriorityQueue queue = new PriorityQueue<>((n1, n2) -> n1.val - n2.val);

然后将 K 个链表的头节点加入到优先级队列中：

for (ListNode list : lists) {

    queue.add(list);    }}

接着，我们依次取出最小的节点，放到新的链表中：

ListNode dummy = new ListNode(0);

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;

OK，我们来看完整的代码：

class Solution {

    // 初始化优先级队列        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;    }}

来看题解的效率：

果然提升了不少。

总结

这道题我们通过**优先级队列 ** PriorityQueue 来实现了合并 K 个升序链表，涉及到了我们之前未曾接触过的数据结构——堆。

最小堆是一种特殊的完全二叉树，满足以下性质：对于树中的每个非叶子节点，节点的值都小于或等于其子节点的值。

记住这个特质。

这样子就能够把最小的元素放在根节点上，的**时间复杂度 **就得到了最小的元素。

怎么实现在的时间内插入一个新元素呢？

要维持 完全二叉树 的特质，就只能在最底层的最右边的叶子节点的右边插入，如果最底层满了，那么就新建一层，再放到这一层中的最左边即可。

如何删除呢？

我们显然不能直接删掉根节点，那样就变成了两个最小堆（小根堆）。

回顾一下这道题所涉及到的 Java 基础知识：

力扣链接：https://leetcode.cn/problems/merge-k-sorted-lists/

一步一个脚印

（优惠券仅 300 张，数量有限）

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412

023.合并 K 个升序链表

题意

难度

标签

示例

分析

初始最小堆

插入新元素

删除最小元素

分析 2

总结

一步一个脚印

题意

难度

标签

示例

分析

初始最小堆

插入新元素

删除最小元素

分析 2

总结

一步一个脚印

题意

难度

标签

示例

分析

初始最小堆

插入新元素

删除最小元素

分析 2

总结

一步一个脚印