当前位置：首页 > 编程日记 > 正文

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

编程日记 2025-01-07 11:40:00

640?wx_fmt=jpeg

作者 | 程序员小吴

转载自五分钟学算法（ID: CXYxiaowu）

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

题目描述

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

示例:

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

输入

输出

题目分析一

这里需要将这 k 个排序链表整合成一个排序链表，也就是说有多个输入，一个输出，类似于漏斗一样的概念。因此，可以利用最小堆的概念。

取每个 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 个链表，处理它们的合并，然后不停的往下划分，直到划分成只有一个或两个链表的任务，开始合并。

代码实现

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

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

（本文为 AI大本营转载文章，转载请微信联系原作者）

◆

实习生招募

◆

640?wx_fmt=jpeg

推荐阅读：

Python超越Java，Rust持续称王！Stack Overflow 2019开发者报告
科大讯飞刷新纪录，机器阅读理解如何超越人类平均水平？技术头条
12个案例教你用Python玩转数据可视化
抵制996！Python之父发声背后，这个社区一呼百应！
刘强东割袍弃兄弟，马爸爸醉心 996
996.ICU 下被过度消费的程序员，还配享受生活吗？
漫画：图的 “最短路径” 问题 | 技术头条
4000万假币流入波场, 发生在凌晨的BTT假币攻击事件始末及细节披露
刺激！我31岁敲代码10年，明天退休！

640?wx_fmt=png

❤点击“阅读原文”，查看更多精彩文章。

https://www.dkcj.cn/info/35238.html

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

题目描述

题目分析一

动画演示

代码实现

题目分析二

代码实现

相关文章：

【Qt】qss样式表之：自定义属性实现动态切换样式

深入学习Lock锁（2）——LockSupport工具类

受用一生的高效PyCharm使用技巧（二）

【GStreamer】基本概念及安装

python学习day3

Visual Studio 2010构建Web浏“.NET研究”览器应用程序

如何通过结构化智能体完成物理构造任务？| 技术头条

【GStreamer】gstreamer工具详解之：gst-launch-1.0

WPF查找子控件和父控件方法

ARP(Accounting Resource Planning)项目感想

【GStreamer】gstreamer工具详解之：gst-inspect-1.0

心酸科研路：3年前CVPR论文，仅被引用11次，如今成就黑洞照片！

Redis和Memcache的区别是什么

windows加载符号小计

谈谈Python那些不为人知的冷知识（一）

【GStreamer】gstreamer工具详解之：ges-launch-1.0

三大软件公司争霸赛区块链

【系列索引】结合项目实例回顾传统设计模式打造属于自己的模式类系列

【GStreamer】gstreamer工具详解之：gst-discoverer-1.0

一道简约而不简单的算法题——数据流的中位数 | 附动画解析

HBase安装与命令行操作

zip/unzip 命令

《App架构师实践指南》：移动开发的进阶指南

FoveaBox：目标检测新纪元，无Anchor时代来临 | 技术头条

【Ubuntu】安装中文输入法、终端不支持中文的解决方法

CCNA 第一章网际互联

【Cmake】执行cmake命令时报错：No XSLT processor found

一张“黑洞”需要拍两年？有了它或许就不会让大家等那么久了

如何在一场面试中展现你对Python的coding能力？| 技术头条

Django web : CSRF verification failed. Request aborted.