当前位置: 首页 > news >正文

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(nlog⁡n) 的时间复杂度和 O(1) 的空间复杂度,时间复杂度是 O(nlog⁡n) 的排序算法包括归并排序、堆排序和快速排序(快速排序的最差时间复杂度是 O(n ^ 2)),其中最适合链表的排序算法是归并排序。

归并排序基于分治算法。最容易想到的实现方式是自顶向下的递归实现,考虑到递归调用的栈空间,自顶向下归并排序的空间复杂度是 O(log⁡n)。如果要达到 O(1) 的空间复杂度,则需要使用自底向上的实现方式。

思路1:自顶向下归并排序

对链表自顶向下归并排序的过程如下。

  1. 找到链表的中点,以中点为分界,将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法,快指针每次移动 22 步,慢指针每次移动 11 步,当快指针到达链表末尾时,慢指针指向的链表节点即为链表的中点。
  2. 对两个子链表分别排序。
  3. 将两个排序后的子链表合并,得到完整的排序后的链表。可以使用「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(nlog⁡n),其中 n 是链表的长度。
  • 空间复杂度:O(log⁡n),其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间。

思路2:自底向上归并排序

使用自底向上的方法实现归并排序,则可以达到 O(1) 的空间复杂度。

首先求得链表的长度 length,然后将链表拆分成子链表进行合并。

具体做法如下。

  1.  用 subLength 表示每次需要排序的子链表的长度,初始时 subLength=1。
  2. 每次将链表拆分成若干个长度为 subLength 的子链表(最后一个子链表的长度可以小于 subLength),按照每两个子链表一组进行合并,合并后即可得到若干个长度为 subLength×2 的有序子链表(最后一个子链表的长度可以小于 subLength×2)。合并两个子链表仍然使用「21. 合并两个有序链表」的做法。
  3. 将 subLength 的值加倍,重复第 2 步,对更长的有序子链表进行合并操作,直到有序子链表的长度大于或等于 length,整个链表排序完毕。

如何保证每次合并之后得到的子链表都是有序的呢?可以通过数学归纳法证明。

  1. 初始时 subLength=1,每个长度为 1 的子链表都是有序的。
  2. 如果每个长度为 subLength 的子链表已经有序,合并两个长度为 subLength 的有序子链表,得到长度为 subLength×2 的子链表,一定也是有序的。
  3. 当最后一个子链表的长度小于 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(nlog⁡n),其中 n 是链表的长度。

  • 空间复杂度:O(1)。

相关文章:

73-归并排序练习-LeetCode148排序链表

题目 给你链表的头结点 head &#xff0c;请将其按升序排列并返回排序后的链表 。 示例 1&#xff1a; 输入&#xff1a;head [4,2,1,3] 输出&#xff1a;[1,2,3,4] 示例 2&#xff1a; 输入&#xff1a;head [-1,5,3,4,0] 输出&#xff1a;[-1,0,3,4,5] 示例 3&#xff…...

Hystrix学习笔记

Hystrix 官方文档&#xff1a; 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 语法格式 说明&#xff1a; 8.1.2 包的作用 8.1.3 应用举例 举例2&#xff1a;MVC设计模式 8.1.4 JDK中主要的包介绍 8.2 import(导入) 8.2.1 语法格式 8.2.2 应用举例 8.2.3 注意事项 8.1 package(包) package&#xff0c;称为包&#x…...

【机器学习】P10 从头到尾实现一个线性回归案例

这里写自定义目录标题&#xff08;1&#xff09;导入数据&#xff08;2&#xff09;画出城市人口与利润图&#xff08;3&#xff09;计算损失值&#xff08;4&#xff09;计算梯度下降&#xff08;5&#xff09;开始训练&#xff08;6&#xff09;画出训练好的模型&#xff08;…...

【Java EE】-多线程编程(四) 死锁

作者&#xff1a;学Java的冬瓜 博客主页&#xff1a;☀冬瓜的主页&#x1f319; 专栏&#xff1a;【JavaEE】 分享&#xff1a;2023.3.31号骑行的照片再发一次(狗头)。 主要内容&#xff1a;什么是死锁&#xff1f;不可重入可重入、死锁的三个典型情况&#xff1a;1、一个线程一…...

学习数据结构第1天(数据结构的基本概念)

数据结构的基本概念基本概念和术语数据结构的三要素经典试题基本概念和术语 1.数据 数据是信息的载体&#xff0c;是描述客观事物属性的数、字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。 2.数据元素 数据元素是数据的基本…...

南大通用数据库-Gbase-8a-学习-33-空洞率查询与解决方法

目录 一、个人理解 二、存储过程 三、虚机测试 四、解决方法 1、重建表 2、shrink space 一、个人理解 空洞率的产生是由于delete语句并不会真实的删除数据&#xff0c;只是在数据上打了一个不可见标签&#xff0c;但实际还是占用着相应的存储空间。 二、存储过程 自定义…...

为什么我们认为GPT是一个技术爆炸

从23年初&#xff0c;ChatGPT火遍全球&#xff0c;通过其高拟人化的回答模式&#xff0c;大幅提升了人机对话的体验和效率&#xff0c;让用户拥有了一个拥有海量知识的虚拟助手&#xff0c;根据UBS发布的研究报告显示&#xff0c;ChatGPT在1月份的月活跃用户数已达1亿&#xff…...

程序员如何能提高自己的编程水平?

这些实用的小建议&#xff0c;能帮你迅速地提高编程水平&#xff1a; 不要做无意义的奋斗 拒绝喊口号和无意义的奋斗&#xff0c;包括但不限于&#xff1a; ①做了计划表却从未有执行的一天&#xff1b; ②每天都是最早来、最晚走&#xff0c;但是工作进度趋近于0&#xff1b…...

从零使用vuepress搭建个人博客部署.github.io

前言 记录小白如何搭建个人博客 github部署的博客&#x1f449;&#xff1a; DreamLuffe的博客 netilify部署的博客&#xff1a;&#x1f449;&#xff1a;DreamLuffe的博客 个人博客搭建实战 网上有很多优秀的开源博客页面&#xff0c;我们就直接安装好&#xff0c;再继续…...

Python 进阶指南(编程轻松进阶):十一、注释、文档字符串和类型提示

原文&#xff1a;http://inventwithpython.com/beyond/chapter11.html 源代码中的注释和文档可能和代码一样重要。原因是软件是永远不会完成的&#xff1b;无论是添加新功能还是修复错误&#xff0c;您总是需要做出改变。但是你不能改变代码&#xff0c;除非你理解它&#xff0…...

python item()方法

Python中有很多方法来解决一些简单的问题&#xff0c;其中最常见的就是用 item &#xff08;&#xff09;方法来完成。item &#xff08;&#xff09;方法的全称是item-process &#xff08;&#xff09;&#xff0c;该方法用来对对象进行创建、删除、改变、添加、更新等操作。…...

【day2】Android Jetpack Compose环境搭建

【day2】Android Jetpack Compose环境搭建 以下是适用于 Jetpack Compose 的环境要求&#xff1a; Android Studio 版本&#xff1a;4.2 Canary 15 或更高版本Gradle 版本&#xff1a;7.0.0-beta02 或更高版本Android 插件版本&#xff1a;4.2.0-beta15 或更高版本Kotlin 版本…...

stable-diffusion安装和简单测试

参考&#xff1a; https://github.com/CompVis/stable-diffusion 理解DALLE 2&#xff0c; 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) +…...

【软考五】数据库(做题)

该文章不适合学习数据库&#xff0c;适合考证&#xff0c;遇到实际问题的&#xff0c;不要在这儿浪费时间。切记切记 软考之数据库一、概念数据模型&#xff08;下午题常考&#xff09;二、结构数据模型关系模型1、关系模型中基本术语2、关系模型中的关系完整性约束3、关系代数…...

【Java Web】012 -- SpringBootWeb综合案例(登录功能、登录校验、异常处理)

目录 一、登录功能 1、基础登录功能 ①、SQL语句 ②、接口参数 ③、实现思路 ④、实现步骤 2、联调Bug&#xff08;没有Cookie或Session&#xff09; 二、登录校验 1、登录校验的实现思路 2、会话技术 ①、会话与会话跟踪 ②、会话跟踪方案对比 Cookie Session …...

跨界智能手表:比亚迪向左,小鹏向右

如今&#xff0c;电动化、智能化是汽车行业转型的大方向&#xff0c;而由于目前国内汽车产业在电动化方面已经算是“小有成效”&#xff0c;因此&#xff0c;抢占智能化高地&#xff0c;打造一个多设备互融的生态系统&#xff0c;就成为了车企的共同愿景。在此背景下&#xff0…...

【c++初阶】第九篇:vector(常用接口的使用 + 模拟实现)

文章目录vector介绍vector的使用vector的定义vector iterator(迭代器) 的使用begin和endrbegin和rendvector 空间增长问题size和capacityreserve和resize&#xff08;重点&#xff09;测试vector的默认扩容机制emptyvector的增删查改push_back和pop_backinsert和erasefindswapo…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...