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

【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——排序链表】

文章目录排序链表二、解题思路&#xff1a;二.实现的代码总结&#xff1a;排序链表 一道链表排序题&#xff0c;链接在这里 二、解题思路&#xff1a; 解题思路&#xff1a;使用归并排序&#xff08;用递归实现&#xff09; 第一步&#xff1a;先找到链表的中间节点 第二步…...

二叉树的遍历(前序、中序、后序)| C语言

目录 0.写在前面 1.前序遍历 步骤详解 代码实现 2.中序遍历 步骤详解 代码实现 3.后序遍历 步骤详解 代码实现 0.写在前面 认识二叉树结构最简单的方式就是遍历二叉树。所谓遍历二叉树就是按照某种特定的规则&#xff0c;对二叉树的每一个节点进行访问&#xff0c;…...

【建议收藏】深入浅出Yolo目标检测算法(含Python实现源码)

深入浅出Yolo目标检测算法&#xff08;含Python实现源码&#xff09; 文章目录深入浅出Yolo目标检测算法&#xff08;含Python实现源码&#xff09;1. One-stage & Two-stage2. Yolo详解2.1 Yolo命名2.2 端到端输入输出2.3 Yolo中的标定框2.4 Yolo网络结构2.5 Yolo的算法流…...

Vue常见的事件修饰符

前言 vue一共给我们准备了6个事件修饰符&#xff0c;前三个比较常用&#xff0c;后三个少见&#xff0c;这里着重讲下前三个 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本文主要介绍卷积神经网络中常用的激活函数及其各自的优缺点 最简单的激活函数被称为线性激活&#xff0c;其中没有应用任何转换。 一个仅由线性激活函数组成的网络很容易训练&#xff0c;但不能学习…...

刷题记录:牛客NC24048[USACO 2017 Jan P]Promotion Counting 求子树的逆序对个数

传送门:牛客 题目描述 奶牛们又一次试图创建一家创业公司&#xff0c;还是没有从过去的经验中吸取教训–牛是可怕的管理者&#xff01; 为了方便&#xff0c;把奶牛从 1∼n1\sim n1∼n 编号&#xff0c;把公司组织成一棵树&#xff0c;1 号奶牛作为总裁&#xff08;这棵树的根…...

MpAndroidChart3最强实践攻略

本篇主要总结下Android非常火爆的一个三方库MpAndroidChart的使用。可能在大多数情况下&#xff0c;我们很少会在Android端去开发图表。但如果说去做一些金融财经类、工厂类、大数据类等的app&#xff0c;那么绝对会用到MpAndroidChart。 一、前言 2018年&#xff0c;那年的我…...

Spring笔记(9):事务管理ACID

一、事务管理 一个数据库事务是一个被视为单一的工作单元操作序列。 事务管理有四个原则&#xff0c;被成为ACID&#xff1a; Atomicity 原子性—— 事务作为独立单元进行操作&#xff0c;整个序列是一体的&#xff0c;操作全都成功或失败。Consistency 一致性—— 引用完整…...

io流 知识点+代码实例

需求 : 如何实现读写文件内部的内容?流 : 数据以先入先出的方式进行流动相当于管道,作用用来传输数据数据源-->流-->目的地流的分类 :流向分 : 以程序为中心输入流输出流操作单元 :字节流 : 万能流字符流 : 只能操作纯文本文件功能分 :节点流 : 真实实现读写的功能流(包…...

【MySQL】P8 多表查询(2) - 连接查询 联合查询

连接查询以及联合查询多表查询概述连接查询内连接隐式内连接显式内连接外连接左外连接右外连接自连接联合查询多表查询概述 建表语句见上一篇博文&#xff1a;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之后&#xff0c;引入Animator动画元素。这种方式可以直接所用于Qt Quick的场景图形系统&#xff0c;这使得基于Animator元素的动画及时在ui界面线程阻塞的情况下仍然能通过图形系统的渲染线程来工作&#xff0c;比传统的基于对象和属性的Animation元素能带来更好的用户…...

Git 分支操作【解决分支冲突问题】

1. 什么是分支 在版本控制过程中&#xff0c;同时推进多个任务&#xff0c;为每个任务&#xff0c;我们就可以创建每个任务的单独分支。使用分支意味着程序员可以把自己的工作从开发主线上分离开来&#xff0c;开发自己分支的时候&#xff0c;不会影响主线分支的运行。对于初学…...

盘点全球10大女性技术先驱

盘点全球10大女性技术先驱 人们普遍认为技术是男性主导的领域&#xff0c;但事实&#xff0c;技术或编程与性别无关&#xff0c;几乎任何人都可以成为技术大神。已经有很多案例证明女性同样可以在技术领域施展才能。在女神节来临之际&#xff0c;我为大家盘点一下为编程做出卓越…...

C++之dynamic_cast

C之dynamic_cast前言dynamic_castNote:示例:前言 dynamic_cast运算符牵扯到的面向对象的多态性跟程序运行时的状态&#xff0c;所以不能完全的使用传统的转换方式来替代。因此是最常用&#xff0c;最不可缺少的一个运算符&#xff0c;与static_cast一样&#xff0c;dynamic_cas…...

JavaScript 箭头函数、函数参数

箭头函数&#xff1a; 箭头函数是一种更加简洁的函数书写方式箭头函数本身没有作用域&#xff08;无this&#xff09;箭头函数的this指向上一层&#xff0c;上下文决定其this基本语法&#xff1a;参数 > 函数体 a. 基本用法 let fn v > v; //等价于 let fn function(…...

JavaScript_Object.keys() Object.values()

目录 一、Object.keys() 二、Object.values() 一、Object.keys() Object.keys( ) 的 用法 : 作用 &#xff1a;遍历对象 { } 返回结果&#xff1a;返回 对象中 每一项 的 key 值 返回值 : 是一个 *** [ 数 组 ] *** 例子 ( 1 ) : <script>// 1. 定义一个对象var obj …...

扬帆优配|高送转+高分红+高增长潜力股揭秘

高送转且高分红的高增加股票&#xff0c;有望跑赢大盘。 此前七连阴的泽宇智能&#xff0c;今日早盘大幅高开。到上午收盘&#xff0c;该股飙涨9.3%&#xff0c;位居涨幅榜前列。音讯面上&#xff0c;3月7日晚间&#xff0c;泽宇智能发表2022年年报&#xff0c;年报显现&#x…...

基于transformer的多帧自监督深度估计 Multi-Frame Self-Supervised Depth with Transformers

Multi-Frame Self-Supervised Depth with Transformers基于transformer的多帧自监督深度估计0 Abstract 多帧深度估计除了学习基于外观的特征外&#xff0c;也通过特征匹配利用图像之间的几何关系来改善单帧估计。我们采用深度离散的核极抽样来选择匹配像素&#xff0c;并通过一…...

设计模式: 单例模式

目录单例模式应用场景实现步骤涉及知识点设计与实现单例模式 通过单例模式的方法创建的类在当前进程中只有一个实例&#xff1b; 应用场景 配置管理 日志记录 线程池 连接池 内存池 对象池 消息队列 实现步骤 将类的构造方法定义为私有方法 定义一个私有的静态实例 提供一…...

idea编辑XML文件出现:Tag name expected报错

说明 Tag name expected解释其实就是&#xff1a;需要标记名称&#xff0c;也就是符号不能直接使用的意思 XML (eXtensible Markup Language) 是一种标记语言&#xff0c;用于存储和传输数据。在 XML 中&#xff0c;有些字符被视为特殊字符&#xff0c;这些字符在 XML 中具有…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

FFmpeg 低延迟同屏方案

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

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...