【leetcode热题】排序链表

给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。

示例 1:

输入:head = [4,2,1,3]
输出:[1,2,3,4]

示例 2:

输入:head = [-1,5,3,4,0]
输出:[-1,0,3,4,5]

示例 3:

输入:head = []
输出:[]

解法一

归并排序需要一个辅助方法,也就是对两个有序链表进行合并,在 21 题 已经讨论过。

至于归并排序的思想,这里就不多讲了,本科的时候用 Scratch 做过一个演示视频,感兴趣的可以参考 这里,哈哈。

那就直接放代码了。因为归并排序是一半一半的进行,所以需要找到中点。最常用的方法就是快慢指针去找中点了。

ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy;
ListNode slow = dummy;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}

上边的代码我加了一个 dummy 指针,就是想当节点个数是偶数的时候,让 slow 刚好指向前边一半节点的最后一个节点,也就是下边的状态。

1    2    3    4
     ^         ^
    slow      fast

如果 slow 和 fast 都从 head 开始走,那么当 fast 结束的时候,slow 就会走到后边一半节点的开头了。

当然除了上边的方法,在 这里 看到,还可以加一个 pre 指针,让它一直指向 slow 的前一个即可。

// step 1. cut the list to two halves
ListNode prev = null, slow = head, fast = head;

while (fast != null && fast.next != null) {
    prev = slow;
    slow = slow.next;
    fast = fast.next.next;
}

他们的目的都是一样的,就是为了方便的把两个链表平均分开。

public ListNode sortList(ListNode head) {
    return mergeSort(head);
}

private ListNode mergeSort(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode fast = dummy;
    ListNode slow = dummy;
    //快慢指针找中点
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    ListNode head2 = slow.next;
    slow.next = null;
    head = mergeSort(head);
    head2 = mergeSort(head2);
    return merge(head, head2);

}

private ListNode merge(ListNode head1, ListNode head2) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    while (head1 != null && head2 != null) {
        if (head1.val < head2.val) {
            tail.next = head1;
            tail = tail.next;
            head1 = head1.next;
        } else {
            tail.next = head2;
            tail = tail.next;
            head2 = head2.next;
        }

    }
    if (head1 != null) {
        tail.next = head1;
    }

    if (head2 != null) {
        tail.next = head2;
    }

    return dummy.next;

}

当然严格的说,上边的解法空间复杂度并不是 O(1),因为递归过程中压栈是需要消耗空间的,每次取一半,所以空间复杂度是 O(log(n))

递归可以去改写成迭代的形式,也就是自底向上的走,就可以省去压栈的空间,空间复杂度从而达到 O(1),详细的可以参考 这里-with-o(1)-space-complextity-and-o(nlgn)-time-complextity) 。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/447144.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

人工智能OCR领域安全应用措施

引言 编写目的 随着新一轮科技革命和产业变革的深入发展&#xff0c;5G、大数据、云计算、深度学习等新技术日益成为推动社会进步的核心动力。人工智能&#xff08;AI&#xff09;作为这些新技术的集大成者&#xff0c;正迅速成为新型基础设施建设的战略性支柱&#xff0c;其广…

Spring Boot整合MyBatis Plus配置多数据源

Spring Boot 专栏&#xff1a;https://blog.csdn.net/dkbnull/category_9278145.html Spring Cloud 专栏&#xff1a;https://blog.csdn.net/dkbnull/category_9287932.html GitHub&#xff1a;https://github.com/dkbnull/SpringBootDemo Gitee&#xff1a;https://gitee.com/…

数字化转型导师坚鹏:科技金融政策、案例及营销创新

科技金融政策、案例及营销创新 课程背景&#xff1a; 很多银行存在以下问题&#xff1a; 不清楚科技金融有哪些利好的政策&#xff1f; 不知道科技金融有哪些成功的案例&#xff1f; 不知道科技金融如何进行营销创新&#xff1f; 课程特色&#xff1a; 以案例的方式解…

Tomcat容器经常重启问题排查

报错代码: INFO [Catalina-utility-2] org.apache.catalina.core.StandardContext.reload Reloading Context with name [] has started1.查看内存占用情况:top 可以发现java线程正常情况下占用高达24%的内存资源 2.继续排查:top -Hp 29580 可以发现主要有子线程Catalina-ut…

基于jsp+mysql+Spring+mybatis的SSM汽车保险理赔管理系统设计和实现

基于jspmysqlSpringmybatis的SSM汽车保险理赔管理系统设计和实现 博主介绍&#xff1a;多年java开发经验&#xff0c;专注Java开发、定制、远程、文档编写指导等,csdn特邀作者、专注于Java技术领域 作者主页 央顺技术团队 Java毕设项目精品实战案例《1000套》 欢迎点赞 收藏 ⭐…

Node-RED在Linux二次开发网关中能源数据实时采集与优化

智能电网与分布式能源系统已成为推动绿色能源转型的重要载体。为了更好地应对多样化的能源供给与需求挑战&#xff0c;以及实现更高效的能源管理&#xff0c;Linux二次开发网关与Node-RED这一创新组合应运而生。 Linux二次开发网关作为高度定制化的硬件平台&#xff0c;其开源特…

MT笔试题

前言 某团硬件工程师的笔试题&#xff0c;个人感觉题目的价值还是很高的&#xff0c;分为选择题和编程题&#xff0c;选择题考的是嵌入式基础知识&#xff0c;编程题是两道算法题&#xff0c;一道为简单难度&#xff0c;一道为中等难度 目录 前言选择题编程题 选择题 C语言中变…

【MATLAB】语音信号识别与处理:一维信号NLM非局部均值滤波算法去噪及谱相减算法呈现频谱

1 基本定义 一维信号NLM非局部均值滤波算法是一种基于非局部均值思想的滤波方法&#xff0c;它通过对信号进行分块&#xff0c;计算每个块与其他块之间的相似度&#xff0c;以非局部均值的方式去除噪声。该算法的主要思想是在一定范围内寻找与当前块相似的块&#xff0c;以这些…

基于网络爬虫的购物平台价格监测系统的设计与实现

通过对网络爬虫的购物平台价格监测系统的业务流程进行梳理可知&#xff0c;网络爬虫的购物平台价格监测系统主要由前台买家模块、后台卖家模块以及管理员模块构成。前台功能包含登录功能、注册功能、系统首页功能、唯品会商品详情浏览、唯品会商品收藏、唯品会商品点赞、唯品会…

RDD算子介绍(二)

1. coalesce 用于缩减分区&#xff0c;减少分区个数&#xff0c;减少任务调度成本。 val rdd : RDD[Int] sc.makeRDD(List(1, 2, 3, 4), 4) val newRDD rdd.coalesce(2) newRDD.saveAsTextFile("output") 分区数可以减少&#xff0c;但是减少后的分区里的数据分布…

政安晨:【深度学习处理实践】(五)—— 初识RNN-循环神经网络

RNN&#xff08;循环神经网络&#xff09;是一种在深度学习中常用的神经网络结构&#xff0c;用于处理序列数据。与传统的前馈神经网络不同&#xff0c;RNN通过引入循环连接在网络中保留了历史信息。 RNN中的每个神经元都有一个隐藏状态&#xff0c;它会根据当前输入和前一个时…

SRS(Simple Realtime Server)

SRS(Simple Realtime Server - github) SRS 中文官网 docker安装srs ##&#xff08;安全组放开1935端口、8080端口&#xff09; docker run --rm -it -p 1935:1935 -p 1985:1985 -p 8080:8080 -p 8000:8000/udp -p 10080:10080/udp ossrs/srs:5推流 ## 不需要加端口 ffmpeg…

深度学习armv8/armv9 cache的原理

文章目录 1、为什么要用cache?2、背景:架构的变化?2、cache的层级关系 ––big.LITTLE架构&#xff08;A53为例)3、cache的层级关系 –-- DynamIQ架构&#xff08;A76为例)4、DSU / L3 cache5、L1/L2/L3 cache都是多大呢6、cache相关的术语介绍7、cache的分配策略(alocation,…

Python读取influxDB数据库

1. influxDB连接 首先用InfluxDBStudio软件连接influxDB数据库来查看所有表&#xff1a; 2. 写sql语句来查询数据 然后和平时写sql查询语句一样&#xff0c;先创建连接client&#xff0c;然后调用其query函数来查询获取数据 self.client influxdb.InfluxDBClient(hostinflu…

前端文件上传

文件上传方式 前端文件上传有两种方式&#xff0c;第一种通过二进制blob传输&#xff08;formData传输&#xff09;&#xff0c;第二种是通过base64传输 文件相关的对象 file对象其实是blob的子类 blob对象的第一个参数必须是一个数组&#xff0c;你可以把一个file对象放进去…

HCS-华为云Stack-计算节点内部网络结构

HCS-华为云Stack-计算节点内部网络结构 图中表示的仅为计算节点是两网口的模式&#xff0c;如果是四网口模式&#xff0c;系统会再自动创建一个网桥出来 图中未画出存储平面和Internal Base平面&#xff0c;它们和tunnel bearing、External OM-样&#xff0c;都是通过trunk0的…

模型驱动架构MDA

MDE 模型驱动工程&#xff08;MDE, Model-Driven Engineering&#xff09;是软件工程的一个分支&#xff0c;它将模型与建模拓展到软件开发的所有方面&#xff0c;形成一个多维建模空间&#xff0c;从而将工程活动建立在这些模型的映射和转换之上。[1] MDE的基本原则是将模型视…

《量子计算:下一个大风口,还是一个热炒概念?》

引言 量子计算,作为一项颠覆性的技术,一直以来备受关注。它被认为是未来计算领域的一次革命,可能改变我们对计算能力和数据处理的理解。然而,随着技术的不断进步和商业应用的探索,人们开始思考,量子计算到底是一个即将到来的大风口,还是一个被过度炒作的概念? 量子计…

空间复杂度(数据结构)

概念&#xff1a; 空间复杂度也是一个数学表达式&#xff0c;是对一个算法在运行过程中临时占用存储空间大小的量度 。 空间复杂度不是程序占用了多少bytes的空间&#xff0c;因为这个也没太大意义&#xff0c;所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复…

软考73-上午题-【面向对象技术2-UML】-UML中的图4

一、构件图&#xff08;组件图&#xff09; 1-1、构件图的定义 展现了&#xff0c;一组构件之间的组织和依赖。 构件图专注于系统的静态实现图。 构件图与类图相关&#xff0c;通常把构件映射为一个、多个类、接口、协作。 【回顾】&#xff1a; 类图展示了一组对象、接口、…