Leetcode 排序链表

embedded/2024/12/27 2:49:04/

在这里插入图片描述
这段代码的算法思想是 归并排序,一种适合链表的排序方法。它通过递归地将链表拆分成两部分,分别排序,然后合并已排序的部分,从而达到整体排序的目的。以下是代码的中文解释:

算法步骤:

  1. 找到链表的中点

    • getMid 方法中,使用了快慢指针(slowfast 指针)来找到链表的中间节点。
    • fast 指针每次移动两步,slow 指针每次移动一步。当 fast 指针到达链表末尾时,slow 指针刚好位于链表中间。
    • 链表分为左右两部分,slow 为中间节点,从而将链表一分为二。
  2. 递归地排序两部分链表

    • sortList 方法中,通过递归地对左半部分和右半部分链表进行排序。递归的终止条件是链表为空或只有一个节点,这时链表已是有序的。
    • 对左右两部分链表分别调用 sortList 方法,进行递归排序,最终会得到两个已排序的子链表
  3. 合并两个有序链表

    • merge 方法用于合并两个已排序的链表,使用的是“归并”的思想。
    • 创建一个虚拟节点 dummy 来帮助合并,将指针 current 初始化为 dummy
    • 遍历两个链表 leftright,比较当前节点的值,将较小的节点连接到 current 节点的后面,然后移动指针。
    • 最后,将剩余的节点(若有)连接到合并后的链表末尾。
    • dummy.next 即为合并后有序链表的头节点。

代码的时间复杂度和空间复杂度:

  • 时间复杂度:归并排序的时间复杂度为 (O(n \log n)),其中 (n) 是链表的节点数,因为每次将链表分成两部分,递归深度为 ( \log n ),而每次合并的时间复杂度是 (O(n))。
  • 空间复杂度:由于递归调用的栈空间,空间复杂度为 (O(\log n))。

总结:

这段代码利用归并排序对链表进行排序,适合链表这种数据结构。链表不支持随机访问,因此归并排序比快速排序更适合链表排序问题。在链表中,归并排序可以通过递归将链表拆分、排序和合并,达到高效排序的目的。

/*** 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 || head.next == null) {return head;}ListNode mid = getMid(head);ListNode left = head;ListNode right = mid.next;mid.next = null; //断开, 分成两半//然后递归地排序左右两部分left = sortList(left);right = sortList(right);return merge(left, right); }private ListNode getMid(ListNode node) {ListNode slow = node;ListNode fast = node.next;while(fast != null && fast.next != null) { //这里是且条件slow = slow.next;fast = fast.next.next; //fast走两步,使用两次next}return slow;}private ListNode merge(ListNode left, ListNode right) {ListNode dummy = new ListNode(0);ListNode current = dummy;while(left != null && right != null) {if(left.val < right.val) {current.next = left;left = left.next;}else {current.next = right;right = right.next;}current = current.next;}if(left != null) {current.next = left;}if(right != null) {current.next = right;}return dummy.next;}
}

http://www.ppmy.cn/embedded/134289.html

相关文章

Python数据分析入门知识基础和案例(万字长文)

目录 数据分析的重要性 Python数据分析工具链 NumPy数组操作 Pandas数据结构与操作 DataFrame操作 Series操作 数据转换 数据清洗 数据分析案例 数据读取与预处理 数据分析 结果展示 Matplotlib基础绘图 线图 柱状图 散点图 PyEcharts交互式图表 可视化案例展…

大模型,多模态大模型面试问题记录【时序,Qformer,卷积,感受野,ControlNet,IP-adapter】

大模型&#xff0c;多模态大模型面试问题记录24/10/27 问题一&#xff1a;视频生成例如Sora或者视频理解internvl2模型怎么提取时序上的特征。问题二&#xff1a;Qformer介绍训练阶段一训练阶段二 问题三&#xff1a;卷积维度计算公式&#xff0c;感受野1. 卷积层输出高度和宽度…

Docker-in-Docker(DinD)

Docker-in-Docker&#xff08;DinD&#xff09;是一种在 Docker 容器内部运行 Docker 引擎的技术。这种方法允许您在一个 Docker 容器内构建和运行其他 Docker 容器。以下是 Docker-in-Docker 的工作原理及其使用场景的详细解释。 工作原理 1.1 Docker 引擎的架构 Docker 引擎…

一文总结AI智能体与传统RPA机器人的16个关键区别

基于LLM的AI Agent&#xff08;智能体&#xff09;与**RPA&#xff08;机器人流程自动化&#xff0c;Robotic Process Automation&#xff09;**两种技术在自动化任务领域中扮演着至关重要的角色。AI智能体能够借助LLM拥有极高的灵活性&#xff0c;可以实时理解和响应环境的变化…

PostgreSQL-06-入门篇-集合运算

文章目录 1. UNION 组合多个查询的结果集简介带有 ORDER BY 子句的 UNION设置样例表PostgreSQL UNION 示例1) 简单的 PostgreSQL UNION 示例2) PostgreSQL UNION ALL 示例3) 带 ORDER BY 子句 UNION ALL 示例 2. INTERSECT 取交集简介带 ORDER BY 子句的 INTERSECT 操作Postgre…

《Python游戏编程入门》注-第4章6

《Python游戏编程入门》的“轮询鼠标”内容介绍了通过轮询鼠标实现实时显示鼠标位置和按键状态的游戏。 1 游戏介绍 实时显示鼠标位置和按键状态的游戏如图1所示。 图1 实时显示鼠标位置和按键状态 从图1中可以看到&#xff0c;游戏界面主要分为上下两部分。其中&#xff0c…

前端自学资料(笔记八股)分享—CSS(4)

更多详情&#xff1a;爱米的前端小笔记&#xff08;csdn~xitujuejin~zhiHu~Baidu~小红shu&#xff09;同步更新&#xff0c;等你来看&#xff01;都是利用下班时间整理的&#xff0c;整理不易&#xff0c;大家多多&#x1f44d;&#x1f49b;➕&#x1f914;哦&#xff01;你们…

Redis在计数器和人员记录的事务操作应用

文章目录 解决计数器和人员记录的事务操作计数器操作人员记录的事务操作事务&#xff08;Transaction&#xff09;示例&#xff1a;使用事务添加或更新人员记录多路复用&#xff08;Pipeline&#xff09;示例&#xff1a;使用 Pipeline 添加或更新人员记录 注意事项 解决计数器…