LeetCode高频题23. 合并K个升序链表

LeetCode高频题23. 合并K个升序链表

提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题

基础知识：
【1】LeetCode高频题21. 合并两个有序链表
【2】二维数组list，每行长度不同，寻找最窄区间[a,b]，保证list每行至少有一个数在[a,b]上

---

文章目录

• LeetCode高频题23. 合并K个升序链表
• • @[TOC](文章目录)
• 题目
• 一、审题
• 比较油腻，就是扣清楚边界
• 总结

题目

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

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

---

一、审题

示例 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.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

比较油腻，就是扣清楚边界

理解一波
给你的是节点数组，每个节点有自己的一串链表

让你把整体组织起来，返回一个head

本题的基础，和之前讲过的一样
实际上之前那个题，就是这个题目的N=2的状况

【1】LeetCode高频题21. 合并两个有序链表

之前见过类似的这种k容器的排序，其实就是弄一个小根堆heap，冒头出来排序。
本题的解题思想完全跟基础知识【2】一模一样
【2】二维数组list，每行长度不同，寻找最窄区间[a,b]，保证list每行至少有一个数在[a,b]上
你去看看，那边是多个数组list，而这里是链表
结构一模一样
只不过你要确定，每次进小根堆的都是来自同一个位置i的元素。
建议你这俩题，都看一下，这样融会贯通。

另外，小根堆用在哪？
之前见过的关于topK词频那些文档，内存只有K个资源，你需要统计词频最大的那几个单词，也就是这样的用小根堆搞定

比如：

每个位置i的节点，最开始都放入小根堆【排序o(log(n)）速度】

弹出最小值tmp=1节点，cur指向它,ans=cur
ans=1
然后去弹出来的节点tmp那个位置i的后续续节点继续往heap中放，看下图绿色那个3，进heap了

弹出heap中最小的节点tmp=3
cur.next=tmp
继续将tmp这个节点所在位置i的下一个节点放入heap，依次这样操作，很简单，就把ans搞定了

思想是不是很简单？
手撕代码，搞清楚细节就行

//准备小根堆的比较器，按val比
        public class valComparator implements Comparator<ListNode>{
            @Override
             public int compare(ListNode o1, ListNode o2){
                return o1.val - o2.val;//小根堆
            }
         }

        public ListNode mergeKLists(ListNode[] lists) {
            //每个位置i的节点，最开始都放入小根堆【排序o(log(n)）速度】
            if (lists == null || lists.length == 0) return null;

            int N = lists.length;
            PriorityQueue<ListNode> heap = new PriorityQueue<>(new valComparator());

            //最开始每个都放
            for (int i = 0; i < N; i++) {
                if (lists[i] != null) heap.add(lists[i]);
            }
            if (heap.isEmpty()) return null;//没有算了

            //然后开始弹出第一个，作为结果的head
            ListNode ans = heap.poll();
            ListNode cur = ans;//用cur解下一个点
            ListNode tmp = ans;//控制下一个加入小根堆的指针
            if (tmp.next != null) heap.add(tmp.next);

            while (!heap.isEmpty()){
                //不断弹出，直到为空
                tmp = heap.poll();
                cur.next = tmp;
                cur = cur.next;//移动
                if (tmp.next != null) heap.add(tmp.next);//tmp的下一个节点有进来
            }
            //最后ans就已经OK了

            return ans;
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

LeetCode直接测试：


非常稳当
注意，最开时每个节点都放，但是不一定有，可能是[[]]
压根就没有，所以要非null才能放哦

//最开始每个都放
            for (int i = 0; i < N; i++) {
                if (lists[i] != null) heap.add(lists[i]);
            }
1
2
3
4

---

总结

提示：重要经验：

1）这种题目，思想重要，topK资源限制情况下，统计词频最高的那些，或者这种按照不同数组升序情况下，整体排序的事情，都要小根堆，让每个链表都有一个元素在堆中，整体谁小，谁先冒出来。
2）小根堆排序复杂度log(n)速度快，之前咱们求不同数组中，必须包含每个数组至少1个数的最窄区间a–b，那种就是利用小根堆，把每个数组，至少放一个元素在小根堆中，这样弹出来的最小最大值，就是区间，而且还包含至少每个数组一个元素。
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。