【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 中具有…...
React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
Python如何给视频添加音频和字幕
在Python中,给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加,包括必要的代码示例和详细解释。 环境准备 在开始之前,需要安装以下Python库:…...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...
使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度
文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...
【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...
永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器
一、原理介绍 传统滑模观测器采用如下结构: 传统SMO中LPF会带来相位延迟和幅值衰减,并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF),可以去除高次谐波,并且不用相位补偿就可以获得一个误差较小的转子位…...
数据结构:递归的种类(Types of Recursion)
目录 尾递归(Tail Recursion) 什么是 Loop(循环)? 复杂度分析 头递归(Head Recursion) 树形递归(Tree Recursion) 线性递归(Linear Recursion)…...
