LeetCode刷题Java版023.合并 K 个升序链表

作者：沉默王二
发布时间：2022-08-11T10:51:45.025+0800

023.合并 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

分析

我们之前已经解过 021.合并两个有序链表这道题了，题解的思路是通过比较两个链表的头节点，更小的那一个就是新链表的头节点，再往后找出下一个节点，使得两个升序链表能在的时间内合并为一个升序链表，那我们能不能用相同的方法来完成 K 个升序链表的合并呢？

如果挨个合并，就是第一个链表先与第二个链表合并，然后拿这个新的链表再与第三个链表合并……，以此类推，看上去能实现我们的目的，那时间复杂度呢？

很遗憾，这样做的话，我们就忽略了一个重要的地方，那就是新的链表的长度会不断变长，并且第一个链表的元素会不断地被访问，实际上第一个链表被循环访问了kList.length - 1次（kList 为链表数组），第二个链表被循环访问了kList.length - 2次……。

由此可见，这样子的时间复杂度会直线飙升，我们得另寻他路。

参考之前的解题思路，只不过这次我们从kList.length 个链表中找出最小值，再向后移动相应的表头，这样子能如我们所愿吗？

。。。。。。

不，不会，这个解题思路最致命的地方，就是从这kList.length 个链表中找出最小值的时间开销太大了，需要遍历 K 个链表。

那有没有一种快速取出数组中的最小值的数据结构来帮我们加速这个过程呢？

有！

Java的PriorityQueue（优先级队列）为我们提供了一个非常不错的解决方案，通过重写Comparator接口中的compare()方法，定义出优先顺序，让PriorityQueue按照节点（ListNode）的值（val）的大小排序即可。

PriorityQueue 内部实现了非常优秀的算法，可以在的时间内取出链表数组中的最小节点，该节点就是新链表的头节点，找到了头节点，就可以找下一个节点，如果该节点还未添加到优先级队列中，就将其添加进去，这个过程的时间复杂度是。

因为每个节点都要经过上述的过程（取出最小值，再插入PriorityQueue中），所以总的时间复杂度是每个链表的大小之和乘以。

即：

是不是有点绕呢？没事，我们看一下代码就会豁然开朗。

/**

* * 定义一个简单的链表.*

* * 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; }*

* * }*

* /

public class Solution {

static Comparator cmp = new Comparator() {

@Override

public int compare(ListNode o1, ListNode o2) {

//重写compare()方法，自定义PriorityQueue内部顺序

return Integer.compare(o1.val , o2.val );

}

};

public ListNode mergeKLists(ListNode[] kList) {

ListNode res = new ListNode();

// 一个空的头节点

ListNode head = res;

// 一个空的优先级队列

Queue que = new PriorityQueue<>(cmp);

// 依次将 K 个链表的头节点添加进PriorityQueue

// 这样就能找出来最小的那一个

// 假如输入的是[[1,4,5],[1,3,4],[2,6]]

// 此时会对这三个链表进行排序，头节点肯定是数值为 1 的这个节点

for (ListNode listNode : kList)

if (listNode != null)

que.add (listNode);

// 开始遍历队列

while(!que.isEmpty()){

// 取出PriorityQueue的队首元素（为所有链表中的最小节点）

ListNode nowPos = que.poll ();

// 把最小的节点放在空链表的第二位

res.next = nowPos;

// 向后移动

res = res.next ;

// 如果这个链表还没有访问完，则加入PriorityQueue中继续访问

*// *

if(nowPos.next != null)

que.add (nowPos.next );

}

// 返回排序后的新链表，从空节点的下一个开始

return head.next ;

}

是不是很好奇为什么PriorityQueue能有这样子的优秀的时间复杂度呢？

实际上，PriorityQueue内部是通过完全二叉树实现的 小根堆 。

小根堆的本质是一棵 完全二叉树 ，其每个节点都有一个键值，且每个节点的键值都大于等于其父亲的键值。这样子就能够把最小的元素放在根的地方，我们能够直接访问到。

我们肯定不能直接随便找个地方把元素直接插入进去，不然我们辛辛苦苦维护的堆的结构一下子就被破坏了。

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

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

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

解决了插入，那么现在就只剩下删除的问题了，我们显然不能直接一股脑地直接删掉根节点，那样就变成了两个小根堆，难以处理。所以我们一般是将插入操作反过来做，把根节点逐渐调节到叶子节点，然后再删除，这样子就不会改变整个小根堆的特质，而在实际在实现的时候，我们常常将根节点与最后一个节点交换，然后直接删除。但是当前的结构不一定能满足小根堆的特质，所以我们还需要 向下调整 ，一直与两个子节点中比较小的一个交换位置，直到底层。因为树高最多，所以我们最多就调整次。

总结

本次我们通过PriorityQueue快速取出kList中的最小值，并且成功的将其合并为一个新的链表，还学习了PriorityQueue的内部结构——堆，其实困难题联想一下先前做过的，加以钻研，思维迁移之后，便能迎刃而解。

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

023.合并 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

分析

由此可见，这样子的时间复杂度会直线飙升，我们得另寻他路。

参考之前的解题思路，只不过这次我们从kList.length 个链表中找出最小值，再向后移动相应的表头，这样子能如我们所愿吗？

。。。。。。

不，不会，这个解题思路最致命的地方，就是从这kList.length 个链表中找出最小值的时间开销太大了，需要遍历 K 个链表。

那有没有一种快速取出数组中的最小值的数据结构来帮我们加速这个过程呢？

有！

因为每个节点都要经过上述的过程（取出最小值，再插入PriorityQueue中），所以总的时间复杂度是每个链表的大小之和乘以。

即：

是不是有点绕呢？没事，我们看一下代码就会豁然开朗。

/**

* * 定义一个简单的链表.*

* * 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; }*

* * }*

* /

public class Solution {

static Comparator cmp = new Comparator() {

@Override

public int compare(ListNode o1, ListNode o2) {

//重写compare()方法，自定义PriorityQueue内部顺序

return Integer.compare(o1.val , o2.val );

}

};

public ListNode mergeKLists(ListNode[] kList) {

ListNode res = new ListNode();

// 一个空的头节点

ListNode head = res;

// 一个空的优先级队列

Queue que = new PriorityQueue<>(cmp);

// 依次将 K 个链表的头节点添加进PriorityQueue

// 这样就能找出来最小的那一个

// 假如输入的是[[1,4,5],[1,3,4],[2,6]]

// 此时会对这三个链表进行排序，头节点肯定是数值为 1 的这个节点

for (ListNode listNode : kList)

if (listNode != null)

que.add (listNode);

// 开始遍历队列

while(!que.isEmpty()){

// 取出PriorityQueue的队首元素（为所有链表中的最小节点）

ListNode nowPos = que.poll ();

// 把最小的节点放在空链表的第二位

res.next = nowPos;

// 向后移动

res = res.next ;

// 如果这个链表还没有访问完，则加入PriorityQueue中继续访问

*// *

if(nowPos.next != null)

que.add (nowPos.next );

}

// 返回排序后的新链表，从空节点的下一个开始

return head.next ;

}

是不是很好奇为什么PriorityQueue能有这样子的优秀的时间复杂度呢？

实际上，PriorityQueue内部是通过完全二叉树实现的 小根堆 。

我们肯定不能直接随便找个地方把元素直接插入进去，不然我们辛辛苦苦维护的堆的结构一下子就被破坏了。

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

总结

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

023.合并 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

分析

由此可见，这样子的时间复杂度会直线飙升，我们得另寻他路。

参考之前的解题思路，只不过这次我们从kList.length 个链表中找出最小值，再向后移动相应的表头，这样子能如我们所愿吗？

。。。。。。

不，不会，这个解题思路最致命的地方，就是从这kList.length 个链表中找出最小值的时间开销太大了，需要遍历 K 个链表。

那有没有一种快速取出数组中的最小值的数据结构来帮我们加速这个过程呢？

有！

因为每个节点都要经过上述的过程（取出最小值，再插入PriorityQueue中），所以总的时间复杂度是每个链表的大小之和乘以。

即：

是不是有点绕呢？没事，我们看一下代码就会豁然开朗。

/**

* * 定义一个简单的链表.*

* * 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; }*

* * }*

* /

public class Solution {

static Comparator cmp = new Comparator() {

@Override

public int compare(ListNode o1, ListNode o2) {

//重写compare()方法，自定义PriorityQueue内部顺序

return Integer.compare(o1.val , o2.val );

}

};

public ListNode mergeKLists(ListNode[] kList) {

ListNode res = new ListNode();

// 一个空的头节点

ListNode head = res;

// 一个空的优先级队列

Queue que = new PriorityQueue<>(cmp);

// 依次将 K 个链表的头节点添加进PriorityQueue

// 这样就能找出来最小的那一个

// 假如输入的是[[1,4,5],[1,3,4],[2,6]]

// 此时会对这三个链表进行排序，头节点肯定是数值为 1 的这个节点

for (ListNode listNode : kList)

if (listNode != null)

que.add (listNode);

// 开始遍历队列

while(!que.isEmpty()){

// 取出PriorityQueue的队首元素（为所有链表中的最小节点）

ListNode nowPos = que.poll ();

// 把最小的节点放在空链表的第二位

res.next = nowPos;

// 向后移动

res = res.next ;

// 如果这个链表还没有访问完，则加入PriorityQueue中继续访问

*// *

if(nowPos.next != null)

que.add (nowPos.next );

}

// 返回排序后的新链表，从空节点的下一个开始

return head.next ;

}

是不是很好奇为什么PriorityQueue能有这样子的优秀的时间复杂度呢？

实际上，PriorityQueue内部是通过完全二叉树实现的 小根堆 。

我们肯定不能直接随便找个地方把元素直接插入进去，不然我们辛辛苦苦维护的堆的结构一下子就被破坏了。

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

总结

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

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