73-归并排序练习-LeetCode148排序链表
题目
给你链表的头结点 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 = []
输出:[]
提示:
链表中节点的数目在范围 [0, 5 * 10 ^ 4] 内
-10 ^ 5 <= Node.val <= 10 ^ 5
进阶:你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?
「147. 对链表进行插入排序」要求使用插入排序的方法对链表进行排序,插入排序的时间复杂度是 O(n^2),其中 nn 是链表的长度。这道题考虑时间复杂度更低的排序算法。题目的进阶问题要求达到 O(nlogn) 的时间复杂度和 O(1) 的空间复杂度,时间复杂度是 O(nlogn) 的排序算法包括归并排序、堆排序和快速排序(快速排序的最差时间复杂度是 O(n ^ 2)),其中最适合链表的排序算法是归并排序。
归并排序基于分治算法。最容易想到的实现方式是自顶向下的递归实现,考虑到递归调用的栈空间,自顶向下归并排序的空间复杂度是 O(logn)。如果要达到 O(1) 的空间复杂度,则需要使用自底向上的实现方式。
思路1:自顶向下归并排序
对链表自顶向下归并排序的过程如下。
- 找到链表的中点,以中点为分界,将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法,快指针每次移动 22 步,慢指针每次移动 11 步,当快指针到达链表末尾时,慢指针指向的链表节点即为链表的中点。
- 对两个子链表分别排序。
- 将两个排序后的子链表合并,得到完整的排序后的链表。可以使用「21. 合并两个有序链表」的做法,将两个有序的子链表进行并。
上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 11,即当链表为空或者链表只包含 11 个节点时,不需要对链表进行拆分和排序。
class Solution {public ListNode sortList(ListNode head) {return sortList(head, null);}public ListNode sortList(ListNode head, ListNode tail) {if (head == null) {return head;}if (head.next == tail) {head.next = null;return head;}ListNode slow = head, fast = head;while (fast != tail) {slow = slow.next;fast = fast.next;if (fast != tail) {fast = fast.next;}}ListNode mid = slow;ListNode list1 = sortList(head, mid);ListNode list2 = sortList(mid, tail);ListNode sorted = merge(list1, list2);return sorted;}public ListNode merge(ListNode head1, ListNode head2) {ListNode dummyHead = new ListNode(0);ListNode temp = dummyHead, temp1 = head1, temp2 = head2;while (temp1 != null && temp2 != null) {if (temp1.val <= temp2.val) {temp.next = temp1;temp1 = temp1.next;} else {temp.next = temp2;temp2 = temp2.next;}temp = temp.next;}if (temp1 != null) {temp.next = temp1;} else if (temp2 != null) {temp.next = temp2;}return dummyHead.next;}
}
复杂度分析
- 时间复杂度:O(nlogn),其中 n 是链表的长度。
- 空间复杂度:O(logn),其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间。
思路2:自底向上归并排序
使用自底向上的方法实现归并排序,则可以达到 O(1) 的空间复杂度。
首先求得链表的长度 length,然后将链表拆分成子链表进行合并。
具体做法如下。
- 用 subLength 表示每次需要排序的子链表的长度,初始时 subLength=1。
- 每次将链表拆分成若干个长度为 subLength 的子链表(最后一个子链表的长度可以小于 subLength),按照每两个子链表一组进行合并,合并后即可得到若干个长度为 subLength×2 的有序子链表(最后一个子链表的长度可以小于 subLength×2)。合并两个子链表仍然使用「21. 合并两个有序链表」的做法。
- 将 subLength 的值加倍,重复第 2 步,对更长的有序子链表进行合并操作,直到有序子链表的长度大于或等于 length,整个链表排序完毕。
如何保证每次合并之后得到的子链表都是有序的呢?可以通过数学归纳法证明。
- 初始时 subLength=1,每个长度为 1 的子链表都是有序的。
- 如果每个长度为 subLength 的子链表已经有序,合并两个长度为 subLength 的有序子链表,得到长度为 subLength×2 的子链表,一定也是有序的。
- 当最后一个子链表的长度小于 subLength 时,该子链表也是有序的,合并两个有序子链表之后得到的子链表一定也是有序的。
因此可以保证最后得到的链表是有序的。
class Solution {public ListNode sortList(ListNode head) {if (head == null) {return head;}int length = 0;ListNode node = head;while (node != null) {length++;node = node.next;}ListNode dummyHead = new ListNode(0, head);for (int subLength = 1; subLength < length; subLength <<= 1) {ListNode prev = dummyHead, curr = dummyHead.next;while (curr != null) {ListNode head1 = curr;for (int i = 1; i < subLength && curr.next != null; i++) {curr = curr.next;}ListNode head2 = curr.next;curr.next = null;curr = head2;for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {curr = curr.next;}ListNode next = null;if (curr != null) {next = curr.next;curr.next = null;}ListNode merged = merge(head1, head2);prev.next = merged;while (prev.next != null) {prev = prev.next;}curr = next;}}return dummyHead.next;}public ListNode merge(ListNode head1, ListNode head2) {ListNode dummyHead = new ListNode(0);ListNode temp = dummyHead, temp1 = head1, temp2 = head2;while (temp1 != null && temp2 != null) {if (temp1.val <= temp2.val) {temp.next = temp1;temp1 = temp1.next;} else {temp.next = temp2;temp2 = temp2.next;}temp = temp.next;}if (temp1 != null) {temp.next = temp1;} else if (temp2 != null) {temp.next = temp2;}return dummyHead.next;}
}
复杂度分析
-
时间复杂度:O(nlogn),其中 n 是链表的长度。
-
空间复杂度:O(1)。
相关文章:
73-归并排序练习-LeetCode148排序链表
题目 给你链表的头结点 head ,请将其按升序排列并返回排序后的链表 。 示例 1: 输入:head [4,2,1,3] 输出:[1,2,3,4] 示例 2: 输入:head [-1,5,3,4,0] 输出:[-1,0,3,4,5] 示例 3ÿ…...
Hystrix学习笔记
Hystrix 官方文档: https://github.com/Netflix/Hystrix/wiki 是什么 In a distributed environment, inevitably some of the many service dependencies will fail. Hystrix is a library that helps you control the interactions between these distributed …...
面向对象编程(基础)8:关键字:package、import
目录 8.1 package(包) 8.1.1 语法格式 说明: 8.1.2 包的作用 8.1.3 应用举例 举例2:MVC设计模式 8.1.4 JDK中主要的包介绍 8.2 import(导入) 8.2.1 语法格式 8.2.2 应用举例 8.2.3 注意事项 8.1 package(包) package,称为包&#x…...
【机器学习】P10 从头到尾实现一个线性回归案例
这里写自定义目录标题(1)导入数据(2)画出城市人口与利润图(3)计算损失值(4)计算梯度下降(5)开始训练(6)画出训练好的模型(…...
【Java EE】-多线程编程(四) 死锁
作者:学Java的冬瓜 博客主页:☀冬瓜的主页🌙 专栏:【JavaEE】 分享:2023.3.31号骑行的照片再发一次(狗头)。 主要内容:什么是死锁?不可重入可重入、死锁的三个典型情况:1、一个线程一…...
学习数据结构第1天(数据结构的基本概念)
数据结构的基本概念基本概念和术语数据结构的三要素经典试题基本概念和术语 1.数据 数据是信息的载体,是描述客观事物属性的数、字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。 2.数据元素 数据元素是数据的基本…...
南大通用数据库-Gbase-8a-学习-33-空洞率查询与解决方法
目录 一、个人理解 二、存储过程 三、虚机测试 四、解决方法 1、重建表 2、shrink space 一、个人理解 空洞率的产生是由于delete语句并不会真实的删除数据,只是在数据上打了一个不可见标签,但实际还是占用着相应的存储空间。 二、存储过程 自定义…...
为什么我们认为GPT是一个技术爆炸
从23年初,ChatGPT火遍全球,通过其高拟人化的回答模式,大幅提升了人机对话的体验和效率,让用户拥有了一个拥有海量知识的虚拟助手,根据UBS发布的研究报告显示,ChatGPT在1月份的月活跃用户数已达1亿ÿ…...
程序员如何能提高自己的编程水平?
这些实用的小建议,能帮你迅速地提高编程水平: 不要做无意义的奋斗 拒绝喊口号和无意义的奋斗,包括但不限于: ①做了计划表却从未有执行的一天; ②每天都是最早来、最晚走,但是工作进度趋近于0;…...
从零使用vuepress搭建个人博客部署.github.io
前言 记录小白如何搭建个人博客 github部署的博客👉: DreamLuffe的博客 netilify部署的博客:👉:DreamLuffe的博客 个人博客搭建实战 网上有很多优秀的开源博客页面,我们就直接安装好,再继续…...
Python 进阶指南(编程轻松进阶):十一、注释、文档字符串和类型提示
原文:http://inventwithpython.com/beyond/chapter11.html 源代码中的注释和文档可能和代码一样重要。原因是软件是永远不会完成的;无论是添加新功能还是修复错误,您总是需要做出改变。但是你不能改变代码,除非你理解它࿰…...
python item()方法
Python中有很多方法来解决一些简单的问题,其中最常见的就是用 item ()方法来完成。item ()方法的全称是item-process (),该方法用来对对象进行创建、删除、改变、添加、更新等操作。…...
【day2】Android Jetpack Compose环境搭建
【day2】Android Jetpack Compose环境搭建 以下是适用于 Jetpack Compose 的环境要求: Android Studio 版本:4.2 Canary 15 或更高版本Gradle 版本:7.0.0-beta02 或更高版本Android 插件版本:4.2.0-beta15 或更高版本Kotlin 版本…...
stable-diffusion安装和简单测试
参考: https://github.com/CompVis/stable-diffusion 理解DALLE 2, Stable Diffusion和 Midjourney的工作原理 Latent Diffusion Models论文解读 【生成式AI】淺談圖像生成模型 Diffusion Model 原理 【生成式AI】Stable Diffusion、DALL-E、Imagen 背後…...
MATLAB算法实战应用案例精讲-【智能优化算法】 基于帕累托包络的选择算法II(PESA-II)(附MATLAB代码实现)
目录 前言 知识储备 数据包络分析(DEA) 特点 名词解释 类型介绍 案例简介 软件操作(SPSSPRO)...
【华为机试真题详解JAVA实现】—坐标移动
目录 一、题目描述 二、解题代码 一、题目描述 开发一个坐标计算工具, A表示向左移动,D表示向右移动,W表示向上移动,S表示向下移动。从(0,0)点开始移动,从输入字符串里面读取一些坐标,并将最终输入结果输出到输出文件里面。 输入: 合法坐标为A(或者D或者W或者S) +…...
【软考五】数据库(做题)
该文章不适合学习数据库,适合考证,遇到实际问题的,不要在这儿浪费时间。切记切记 软考之数据库一、概念数据模型(下午题常考)二、结构数据模型关系模型1、关系模型中基本术语2、关系模型中的关系完整性约束3、关系代数…...
【Java Web】012 -- SpringBootWeb综合案例(登录功能、登录校验、异常处理)
目录 一、登录功能 1、基础登录功能 ①、SQL语句 ②、接口参数 ③、实现思路 ④、实现步骤 2、联调Bug(没有Cookie或Session) 二、登录校验 1、登录校验的实现思路 2、会话技术 ①、会话与会话跟踪 ②、会话跟踪方案对比 Cookie Session …...
跨界智能手表:比亚迪向左,小鹏向右
如今,电动化、智能化是汽车行业转型的大方向,而由于目前国内汽车产业在电动化方面已经算是“小有成效”,因此,抢占智能化高地,打造一个多设备互融的生态系统,就成为了车企的共同愿景。在此背景下࿰…...
【c++初阶】第九篇:vector(常用接口的使用 + 模拟实现)
文章目录vector介绍vector的使用vector的定义vector iterator(迭代器) 的使用begin和endrbegin和rendvector 空间增长问题size和capacityreserve和resize(重点)测试vector的默认扩容机制emptyvector的增删查改push_back和pop_backinsert和erasefindswapo…...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...
云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...
【若依】框架项目部署笔记
参考【SpringBoot】【Vue】项目部署_no main manifest attribute, in springboot-0.0.1-sn-CSDN博客 多一个redis安装 准备工作: 压缩包下载:http://download.redis.io/releases 1. 上传压缩包,并进入压缩包所在目录,解压到目标…...
SQL注入篇-sqlmap的配置和使用
在之前的皮卡丘靶场第五期SQL注入的内容中我们谈到了sqlmap,但是由于很多朋友看不了解命令行格式,所以是纯手动获取数据库信息的 接下来我们就用sqlmap来进行皮卡丘靶场的sql注入学习,链接:https://wwhc.lanzoue.com/ifJY32ybh6vc…...
