LeetCode 上最难的链表算法题，没有之一！

秒速五厘米 2022-04-24 00:04 108阅读 0赞

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

题目来源于 LeetCode 第 23 号问题：合并 K 个排序链表。

该题在 LeetCode 官网上有关于链表的问题中标注为最难的一道题目：难度为 Hard ，通过率在链表 Hard 级别目前最低。

### 题目描述 ###

合并 *k* 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

**示例:**

输入:
    [
      1->4->5,
      1->3->4,
      2->6
    ]
    输出: 1->1->2->3->4->4->5->6

**输入**

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1] 图一

**输出**

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2] 图二

### 题目分析一 ###

这里需要将这 *k* 个排序链表整合成一个排序链表，也就是说有多个输入，一个输出，类似于漏斗一样的概念。

因此，可以利用最小堆的概念。如果你对堆的概念不熟悉，[可以戳这先了解一下~][Link 1]

取每个 Linked List 的最小节点放入一个 heap 中，排序成最小堆。然后取出堆顶最小的元素，放入输出的合并 List 中，然后将该节点在其对应的 List 中的下一个节点插入到 heap 中，循环上面步骤，以此类推直到全部节点都经过 heap。

由于 heap 的大小为始终为 k ，而每次插入的复杂度是 logk ，一共插入了 nk 个节点。时间复杂度为 O(nklogk)，空间复杂度为O(k)。

### 动画演示 ###

Made by Jun Chen

### 代码实现 ###

class Solution {
        
        public ListNode mergeKLists(ListNode[] lists) {
        
            //用heap(堆)这种数据结构，也就是 java 里面的 PriorityQueue
            PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
        
                public int compare(ListNode a, ListNode b) {
        
                    return a.val-b.val;
                }
            });
            ListNode ret = null, cur = null;
            for(ListNode node: lists) {
        
                if(null != node) {
        
                    pq.add(node);    
                }
            }
            while(!pq.isEmpty()) {
        
                ListNode node = pq.poll();
                if(null == ret) {
        
                    ret = cur = node;
                }
                else {
        
                    cur = cur.next = node;
                }
                if(null != node.next) {
        
                    pq.add(node.next);    
                }
            }
            return ret;
        }
    }

### 题目分析二 ###

这道题需要合并 k 个有序链表，并且最终合并出来的结果也必须是有序的。如果一开始没有头绪的话，可以先从简单的开始：**合并 两 个有序链表**。

合并两个有序链表：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

**示例：**

输入：1->2->4, 1->3->4
    输出：1->1->2->3->4->4

这道题目按照题目描述做下去就行：新建一个链表，比较原始两个链表中的元素值，把较小的那个链到新链表中即可。需要注意的一点时由于两个输入链表的长度可能不同，所以最终会有一个链表先完成插入所有元素，则直接另一个未完成的链表直接链入新链表的末尾。

所以代码实现很容易写：

class Solution {
        
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
            //新建链表
            ListNode dummyHead = new ListNode(0);
            ListNode cur = dummyHead;
            while (l1 != null && l2 != null) {
        
                if (l1.val < l2.val) {
        
                    cur.next = l1;
                    cur = cur.next;
                    l1 = l1.next;
                } else {
        
                    cur.next = l2;
                    cur = cur.next;
                    l2 = l2.next;
                }
            }
            // 注意点：当有链表为空时，直接连接另一条链表
            if (l1 == null) {
        
                cur.next = l2;
            } else {
        
                cur.next = l1;
            }
            return dummyHead.next;
        }

现在回到一开始的题目：合并 K 个排序链表。

**合并 K 个排序链表** 与 **合并两个有序链表** 的区别点在于操作有序链表的数量上，因此完全可以按照上面的代码思路来实现合并 K 个排序链表。

这里可以参考 **归并排序** 的分治思想，将这 K 个链表先划分为两个 K/2 个链表，处理它们的合并，然后不停的往下划分，直到划分成只有一个或两个链表的任务，开始合并。

![640?wx\_fmt=gif][640_wx_fmt_gif] 归并-分治

### 代码实现 ###

根据上面的动画，实现代码非常简单也容易理解，先划分，直到不能划分下去，然后开始合并。

class Solution {
        
        public ListNode mergeKLists(ListNode[] lists){
        
            if(lists.length == 0)
                return null;
            if(lists.length == 1)
                return lists[0];
            if(lists.length == 2){
        
               return mergeTwoLists(lists[0],lists[1]);
            }
    
            int mid = lists.length/2;
            ListNode[] l1 = new ListNode[mid];
            for(int i = 0; i < mid; i++){
        
                l1[i] = lists[i];
            }
    
            ListNode[] l2 = new ListNode[lists.length-mid];
            for(int i = mid,j=0; i < lists.length; i++,j++){
        
                l2[j] = lists[i];
            }
    
            return mergeTwoLists(mergeKLists(l1),mergeKLists(l2));
    
        }
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
            if (l1 == null) return l2;
            if (l2 == null) return l1;
    
            ListNode head = null;
            if (l1.val <= l2.val){
        
                head = l1;
                head.next = mergeTwoLists(l1.next, l2);
            } else {
        
                head = l2;
                head.next = mergeTwoLists(l1, l2.next);
            }
            return head;
        }
    }

**推荐阅读**

[拜托，面试官别问我「布隆」了][Link 2]

[数据结构与算法： 三十张图弄懂「图的两种遍历方式」][Link 3]

[昨天，终于拿到了腾讯 offer][offer]

[几道和「二叉树」有关的算法面试题][Link 4]

[几道和散列（哈希）表有关的面试题][Link 5]

[一道看完答案你会觉得很沙雕的「动态规划算法题」][Link 6]

[几道和「堆栈、队列」有关的面试算法题][Link 7]

[链表算法面试问题？看我就够了！][Link 8]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 3]

欢迎关注![640?wx\_fmt=png][640_wx_fmt_png]

![640][]戳 “阅读原文”前往小吴的个人博客一起充电学习!

[640_wx_fmt_jpeg]: /images/20220222/ea964c49b45740598c66187f479500dc.png
[640_wx_fmt_jpeg 1]: /images/20220222/b1031999574e440a972412e8ada8d23e.png
[640_wx_fmt_jpeg 2]: /images/20220222/a0a43f6ab556473ca526230626be7bd8.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484290&idx=1&sn=971ae3365a8a9d284e427e623d825bba&chksm=fa0e6c03cd79e5155675799b8dff854fd1f0763f8a0991c401e64a549774522cf64b026cb39f&scene=21#wechat_redirect
[640_wx_fmt_gif]: /images/20220222/39ab201f88c74c3787abf2b54de2abba.png
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485011&idx=1&sn=a3031a3d3ad033e44439d42d72753e16&chksm=fa0e69d2cd79e0c45b1eb017c65b60662890f67ec70ef44e92ef7f5cddfc313ea6ab353952f4&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485076&idx=1&sn=ba747d1efd4c009da83681a6bb4ff549&chksm=fa0e6915cd79e003249e9ee045d09a174b0e5aff2a6ecd807e10fd01bfbc1a37da688eb51637&scene=21#wechat_redirect
[offer]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485001&idx=1&sn=cdcebef70aaabcafa3403c2dd51bdfb7&chksm=fa0e69c8cd79e0de12ece3a9e48430099c429aff816cc3a9e40035192dc07a864864888d1078&scene=21#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484985&idx=1&sn=93343d355abf36c77a361c9931cbe2d1&chksm=fa0e69b8cd79e0ae1e6b57665a456da5f421cc92fe6934337f1eb1e18c3fd6a3c1adc8ca88c2&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484977&idx=1&sn=f4a6148480555e3cca83231ac1df8d02&chksm=fa0e69b0cd79e0a686e31c547fc783eb9663d9fe19cc95ecd524e9f8f7e0d4a168945f8755e5&scene=21#wechat_redirect
[Link 6]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484875&idx=1&sn=72cf66da1c970ba345e8b1ab3586c10d&chksm=fa0e6a4acd79e35c32c9201e99cc93a71d0f2a331319addf5303c76ac05738b312ab238a8304&scene=21#wechat_redirect
[Link 7]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484846&idx=2&sn=e508da06e9f7a0b3d00db5415d7ce622&chksm=fa0e6a2fcd79e3397fe8083f9493ae639f47c9448ac2a0026026494d098c47ecc6e08f1f8e28&scene=21#wechat_redirect
[Link 8]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484830&idx=1&sn=9d24fc787da4b49b82ac01c7f8de257b&chksm=fa0e6a1fcd79e309a2e7f3e09ec9913a55f1c077287c907f13528578b7785831a2effb3104e0&scene=21#wechat_redirect
[640_wx_fmt_jpeg 3]: /images/20220222/2a3bd4a451084a7d982d00a6a2ed092f.png
[640_wx_fmt_png]: /images/20220222/100fb819260f41b89a84533cea3e989d.png
[640]: /images/20220222/aaaf543ada0b49f9bd336f9f1ac66c39.png