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…...
idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...
WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...
用docker来安装部署freeswitch记录
今天刚才测试一个callcenter的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...
【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
