【LeetCode——排序链表】
文章目录
- 排序链表
- 二、解题思路:
- 二.实现的代码
- 总结:
排序链表
一道链表排序题,链接在这里

二、解题思路:
解题思路:使用归并排序(用递归实现)
第一步:先找到链表的中间节点

第二步:将链表从中间节点开始断开

找到mid节点(中间节点)的前一个节点,将两个链表断开。
第三步:重复上述操作,再在新链表中找中间节点,再分开,直到分开到链表剩下一个节点为止。

第四步,合并链表。
举个例子:
给两个链表:一个是1->2->3->4,一个链表是0->2->3->5
将这两个有序链表合并成一个有序链表。

申请一个哨兵位的头节点,不存储有效数据,然后使用l1,l2来遍历两个链表,比较l1和l2存储的值的大小。
回到上面的题,两个节点之间两两比较,只要满足升序要求即可。
合并俩节点后,再合并两个链表。

总效果如下图:

二.实现的代码
```c
typedef struct ListNode ListNode;ListNode*midNode(ListNode*head)
{ListNode*fast = head,*slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;}return slow;
}//合并链表
ListNode*mergelist(ListNode*head1,ListNode*head2)
{ListNode*newhead = (ListNode*)malloc(sizeof(ListNode));ListNode*l1 = head1,*l2 = head2,*tail = newhead;while(l1 && l2){if(l1->val <= l2->val){tail->next = l1;l1 = l1->next;}else{tail->next = l2;l2 = l2->next;}tail = tail->next;}if(l1!=NULL){tail->next = l1;}if(l2!=NULL){tail->next = l2;}ListNode*ret = newhead->next;free(newhead);return ret;
}ListNode*tosortList(ListNode*head)
{//空链表和只有一个节点不用再排序了if(head==NULL ||head->next == NULL){return head;}//找中间节点ListNode*mid = midNode(head);//找中间节点的前一个节点ListNode*prev = head;while(prev->next!=mid){prev = prev->next;}//断开链表prev->next = NULL;//返回排序后的新链表的头ListNode*left = tosortList(head);ListNode*right = tosortList(mid);return mergelist(left,right);
}struct ListNode* sortList(struct ListNode* head)
{return tosortList(head);
}
总结:
使用归并排序是解题的较好的方法。
相关文章:
【LeetCode——排序链表】
文章目录排序链表二、解题思路:二.实现的代码总结:排序链表 一道链表排序题,链接在这里 二、解题思路: 解题思路:使用归并排序(用递归实现) 第一步:先找到链表的中间节点 第二步…...
二叉树的遍历(前序、中序、后序)| C语言
目录 0.写在前面 1.前序遍历 步骤详解 代码实现 2.中序遍历 步骤详解 代码实现 3.后序遍历 步骤详解 代码实现 0.写在前面 认识二叉树结构最简单的方式就是遍历二叉树。所谓遍历二叉树就是按照某种特定的规则,对二叉树的每一个节点进行访问,…...
【建议收藏】深入浅出Yolo目标检测算法(含Python实现源码)
深入浅出Yolo目标检测算法(含Python实现源码) 文章目录深入浅出Yolo目标检测算法(含Python实现源码)1. One-stage & Two-stage2. Yolo详解2.1 Yolo命名2.2 端到端输入输出2.3 Yolo中的标定框2.4 Yolo网络结构2.5 Yolo的算法流…...
Vue常见的事件修饰符
前言 vue一共给我们准备了6个事件修饰符,前三个比较常用,后三个少见,这里着重讲下前三个 1.prevent:阻止默认事件(常用) 2. stop:阻止事件冒泡(常用) 3. once:事件只触发一次(常用) 4.captrue:使用事件的捕捉模式(不常用) 5.self:只有event…...
【卷积神经网络】激活函数 | Tanh / Sigmoid / ReLU / Leaky ReLU / ELU / SiLU / GeLU
文章目录一、Tanh二、Sigmoid三、ReLU四、Leaky ReLU五、ELU六、SiLU七、Mish本文主要介绍卷积神经网络中常用的激活函数及其各自的优缺点 最简单的激活函数被称为线性激活,其中没有应用任何转换。 一个仅由线性激活函数组成的网络很容易训练,但不能学习…...
刷题记录:牛客NC24048[USACO 2017 Jan P]Promotion Counting 求子树的逆序对个数
传送门:牛客 题目描述 奶牛们又一次试图创建一家创业公司,还是没有从过去的经验中吸取教训–牛是可怕的管理者! 为了方便,把奶牛从 1∼n1\sim n1∼n 编号,把公司组织成一棵树,1 号奶牛作为总裁(这棵树的根…...
MpAndroidChart3最强实践攻略
本篇主要总结下Android非常火爆的一个三方库MpAndroidChart的使用。可能在大多数情况下,我们很少会在Android端去开发图表。但如果说去做一些金融财经类、工厂类、大数据类等的app,那么绝对会用到MpAndroidChart。 一、前言 2018年,那年的我…...
Spring笔记(9):事务管理ACID
一、事务管理 一个数据库事务是一个被视为单一的工作单元操作序列。 事务管理有四个原则,被成为ACID: Atomicity 原子性—— 事务作为独立单元进行操作,整个序列是一体的,操作全都成功或失败。Consistency 一致性—— 引用完整…...
io流 知识点+代码实例
需求 : 如何实现读写文件内部的内容?流 : 数据以先入先出的方式进行流动相当于管道,作用用来传输数据数据源-->流-->目的地流的分类 :流向分 : 以程序为中心输入流输出流操作单元 :字节流 : 万能流字符流 : 只能操作纯文本文件功能分 :节点流 : 真实实现读写的功能流(包…...
【MySQL】P8 多表查询(2) - 连接查询 联合查询
连接查询以及联合查询多表查询概述连接查询内连接隐式内连接显式内连接外连接左外连接右外连接自连接联合查询多表查询概述 建表语句见上一篇博文:https://blog.csdn.net/weixin_43098506/article/details/129402302 e.g.e.g.e.g. select * from emp, dept where e…...
QML动画(Animator)
在Qt5.2之后,引入Animator动画元素。这种方式可以直接所用于Qt Quick的场景图形系统,这使得基于Animator元素的动画及时在ui界面线程阻塞的情况下仍然能通过图形系统的渲染线程来工作,比传统的基于对象和属性的Animation元素能带来更好的用户…...
Git 分支操作【解决分支冲突问题】
1. 什么是分支 在版本控制过程中,同时推进多个任务,为每个任务,我们就可以创建每个任务的单独分支。使用分支意味着程序员可以把自己的工作从开发主线上分离开来,开发自己分支的时候,不会影响主线分支的运行。对于初学…...
盘点全球10大女性技术先驱
盘点全球10大女性技术先驱 人们普遍认为技术是男性主导的领域,但事实,技术或编程与性别无关,几乎任何人都可以成为技术大神。已经有很多案例证明女性同样可以在技术领域施展才能。在女神节来临之际,我为大家盘点一下为编程做出卓越…...
C++之dynamic_cast
C之dynamic_cast前言dynamic_castNote:示例:前言 dynamic_cast运算符牵扯到的面向对象的多态性跟程序运行时的状态,所以不能完全的使用传统的转换方式来替代。因此是最常用,最不可缺少的一个运算符,与static_cast一样,dynamic_cas…...
JavaScript 箭头函数、函数参数
箭头函数: 箭头函数是一种更加简洁的函数书写方式箭头函数本身没有作用域(无this)箭头函数的this指向上一层,上下文决定其this基本语法:参数 > 函数体 a. 基本用法 let fn v > v; //等价于 let fn function(…...
JavaScript_Object.keys() Object.values()
目录 一、Object.keys() 二、Object.values() 一、Object.keys() Object.keys( ) 的 用法 : 作用 :遍历对象 { } 返回结果:返回 对象中 每一项 的 key 值 返回值 : 是一个 *** [ 数 组 ] *** 例子 ( 1 ) : <script>// 1. 定义一个对象var obj …...
扬帆优配|高送转+高分红+高增长潜力股揭秘
高送转且高分红的高增加股票,有望跑赢大盘。 此前七连阴的泽宇智能,今日早盘大幅高开。到上午收盘,该股飙涨9.3%,位居涨幅榜前列。音讯面上,3月7日晚间,泽宇智能发表2022年年报,年报显现&#x…...
基于transformer的多帧自监督深度估计 Multi-Frame Self-Supervised Depth with Transformers
Multi-Frame Self-Supervised Depth with Transformers基于transformer的多帧自监督深度估计0 Abstract 多帧深度估计除了学习基于外观的特征外,也通过特征匹配利用图像之间的几何关系来改善单帧估计。我们采用深度离散的核极抽样来选择匹配像素,并通过一…...
设计模式: 单例模式
目录单例模式应用场景实现步骤涉及知识点设计与实现单例模式 通过单例模式的方法创建的类在当前进程中只有一个实例; 应用场景 配置管理 日志记录 线程池 连接池 内存池 对象池 消息队列 实现步骤 将类的构造方法定义为私有方法 定义一个私有的静态实例 提供一…...
idea编辑XML文件出现:Tag name expected报错
说明 Tag name expected解释其实就是:需要标记名称,也就是符号不能直接使用的意思 XML (eXtensible Markup Language) 是一种标记语言,用于存储和传输数据。在 XML 中,有些字符被视为特殊字符,这些字符在 XML 中具有…...
业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:
根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...
R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...
Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...
