【LeetCode】【算法】148. 排序链表

LeetCode 148. 排序链表

题目

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

思路

思路:归并排序
第一步:切左右,使用快慢指针找到中间节点
第二步:排左右,根据上面找到的中间节点,左右两个链表作为参数递归调用排序方法
第三步:while(leftNode!=null&&rightNode!=null)判断左右链表的结果,进行归并排序
第四步:对于leftNode!=null / rightNode!=null,把不为空的节点接到排好序的链表后面

代码

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode sortList(ListNode head) {// 归并排序// 返回条件if (head == null) return head;if (head != null && head.next == null) return head;// 切左右ListNode prevSlowNode = head;ListNode slowNode = head;ListNode fastNode = head;while (fastNode != null && fastNode.next != null) {prevSlowNode = slowNode;slowNode = slowNode.next;fastNode = fastNode.next.next;}prevSlowNode.next = null;// 排左右ListNode leftNode = sortList(head); // 排左边ListNode rightNode = sortList(slowNode); // 排右边// 左右归并排序ListNode result = new ListNode(); // dummy headListNode cur = result;while (leftNode != null && rightNode != null) {if (leftNode.val < rightNode.val){cur.next = leftNode;leftNode = leftNode.next;} else {cur.next = rightNode;rightNode = rightNode.next;}cur = cur.next;cur.next = null;}if (leftNode != null){cur.next = leftNode;}if (rightNode != null){cur.next = rightNode;}return result.next;}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Devops业务价值流:软件研发最佳实践

在当今快速迭代的软件开发环境中&#xff0c;DevOps业务价值流已成为推动软件研发高效与质量并重的关键实践。软件研发阶段作为产品生命周期的核心环节&#xff0c;其每一步都承载着将创意转化为现实的重要使命。在历经需求澄清的精准定位、架构设计的宏观规划以及项目初始化的…

wireshark工具使用

复制数据 1.右键展开整帧数据 2.复制“所有可见项目” mark标记数据 标记&#xff1a; 跳转&#xff1a; 保存成文件&#xff1a; 文件–>导出特定分组—>Marked packets only

管理 Elasticsearch 变得更容易了,非常容易!

作者&#xff1a;来自 Elastic Ken Exner Elasticsearch 用户&#xff0c;我们听到了你的心声。管理 Elasticsearch 有时会变得很复杂&#xff0c;面临的挑战包括性能调整、问题检测和资源优化。我们一直致力于简化你的体验。今天&#xff0c;我们宣布了自收购 Opster 以来的一…

深度洞察| 超6亿银发精准流量,40+泛银发群体参与消费三大变化

作者 | NewAgingPro团队 前言 9月24日&#xff0c;AgeClub成立银发流量及场景联盟&#xff08;简称&#xff1a;AgeMCN&#xff09;&#xff0c;助力银发经济高质量发展。 10月11日&#xff0c;AgeClub发布《2024银发流量全景洞察报告》&#xff0c;探索银发流量发展新模式…

Spring Boot——日志介绍和配置

1. 日志的介绍 在前面的学习中&#xff0c;控制台上打印出来的一大堆内容就是日志&#xff0c;可以帮助我们发现问题&#xff0c;分析问题&#xff0c;定位问题&#xff0c;除此之外&#xff0c;日志还可以进行系统的监控&#xff0c;数据采集等 2. 日志的使用 在程序中获取日…

Redis 组网方式入门

文章目录 一、组网方式1. 单实例模式描述优点缺点适用场景 2. 主从复制模式&#xff08;Master-Slave Replication&#xff09;描述优点缺点适用场景基于docker的redis主从复制1. 配置主节点2. 配置从节点3. 查看节点状态4. 验证主从数据同步5. 查看同步进度 3. 哨兵模式&#…

信号-2-信号捕捉

相关概念&#xff1a;递达 未决 / 阻塞 忽略 阻塞 vs 忽略 阻塞&#xff1a; 如果指定信号信号被阻塞&#xff0c; block期间该信号不能被递达&#xff0c;一直在pending表中。知道block被撤销后&#xff0c; 该信号才能递达&#xff0c;递达后对应pending位置置零。 忽…

(蓝桥杯C/C++)——基础算法(下)

目录 一、时空复杂度 1.时间复杂度 2.空间复杂度 3.分析技巧 4.代码示例 二、递归 1.递归的介绍 2.递归如何实现 3.递归和循环的比较 4.代码示例 三、差分 1.差分的原理和特点 2.差分的实现 3.例题讲解 四、枚举 1.枚举算法介绍 2.解空间的类型 3. 循环枚举解…

【极限编程(XP)】

极限编程&#xff08;XP&#xff09;简介 定义与核心价值观&#xff1a;极限编程&#xff08;Extreme Programming&#xff0c;XP&#xff09;是一种轻量级、敏捷的软件开发方法。它强调团队合作、客户参与、持续测试和快速反馈等价值观&#xff0c;旨在提高软件开发的效率和质…

如何编写安全的 Go 代码

原文&#xff1a;Jakub Jarosz - 2024.11.02 在编写 Go 代码时&#xff0c;如何时刻考虑安全性&#xff1f;要在一篇简短的文章中回答这个问题似乎不太可能。因此&#xff0c;我们将把范围缩小到一些具体做法上。 这些实践如果持续应用&#xff0c;将有助于我们编写健壮、安全…

Go八股(Ⅳ)***slice,string,defer***

***slice&#xff0c;string&#xff0c;defer*** 1.slice和arry的区别 arry&#xff1a; Go语言中arry即为数据的一种集合&#xff0c;需要在声明时指定容量和初值&#xff0c;且一旦声明就长度固定&#xff0c;访问时按照索引访问。通过内置函数len可以获取数组中的元素个…

使用 Mac 数据恢复从 iPhoto 图库中恢复照片

我们每个人都会遇到这种情况&#xff1a;在意识到我们不想丢失照片之前&#xff0c;我们会永久删除 iPhoto 图库中的一些照片。永久删除这些照片后&#xff0c;是否可以从 iPhoto 图库中恢复照片&#xff1f;本文将指导您使用免费的 Mac 数据恢复软件从 iPhoto 中恢复照片。 i…

Spark 的介绍与搭建:从理论到实践

目录 一、分布式的思想 &#xff08;一&#xff09;存储 &#xff08;二&#xff09;计算 二、Spark 简介 &#xff08;一&#xff09;发展历程 &#xff08;二&#xff09;Spark 能做什么&#xff1f; &#xff08;三&#xff09;spark 的组成部分 &#xff08;四&…

Spring Boot2(Spring Boot 的Web开发 springMVC 请求处理 参数绑定 常用注解 数据传递 文件上传)

SpringBoot的web开发 静态资源映射规则 总结&#xff1a;只要静态资源放在类路径下&#xff1a; called /static (or /public or /resources or //METAINF/resources 一启动服务器就能访问到静态资源文件 springboot只需要将图片放在 static 下 就可以被访问到了 总结&…

Vue2中使用firefox的pdfjs进行文件文件流预览

文章目录 1.使用场景2. 使用方式1. npm 包下载,[点击查看](https://www.npmjs.com/package/pdfjs-dist)2. 官网下载1. 放到public文件夹下面2. 官网下载地址[点我,进入官网](https://github.com/mozilla/pdf.js/tags?afterv3.3.122) 3. 代码演示4. 图片预览5. 如果遇到跨域或者…

2024软件测试面试热点问题

&#x1f345; 点击文末小卡片 &#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 大厂面试热点问题 1、测试人员需要何时参加需求分析&#xff1f; 如果条件循序 原则上来说 是越早介入需求分析越好 因为测试人员对需求理解越深刻 对测试工…

C语言 | Leetcode C语言题解之第542题01矩阵

题目&#xff1a; 题解&#xff1a; /*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/ type…

C++总结

目录 一、面向对象的三大特性 二、引用 2.1 概念 2.2特性 三、类与对象 3.1概念 3.2 类的内容 3.3对象的创建 四、构造函数与析构函数 五、封装 六、继承 6.1概念与基础使用 6.2 继承权限 6.2.1 权限修饰符 6.2.2 继承权限 6.3构造函数 6.3.1 派生类与基类的构造函数关系 6.3.2…

2024 CSS保姆级教程二 - BFC详解

前言 - CSS中的文档流 在介绍BFC之前&#xff0c;需要先给大家介绍一下文档流。​ 我们常说的文档流其实分为定位流、浮动流、普通流三种。​ ​ 1. 绝对定位(Absolute positioning)​ 如果元素的属性 position 为 absolute 或 fixed&#xff0c;它就是一个绝对定位元素。​ 在…

在PHP8内,用Jenssegers MongoDB扩展来实现Laravel与MongoDB的集成

在现代 web 开发中&#xff0c;MongoDB 作为一种流行的 NoSQL 数据库&#xff0c;因其灵活的文档结构和高性能而受到许多开发者的青睐。Laravel&#xff0c;作为一个优雅的 PHP Web 框架&#xff0c;提供了丰富的功能和优雅的代码风格。本文将指导你如何在 Laravel 项目中集成 …