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

代码练习12-排序链表

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

归并排序算法核心步骤

归并排序核心步骤如下:

  • 把长度为n的要排序的序列,分成两个长度为n/2的子序列;
  • 对这两个子序列,分别采用归并排序;
  • 将两个排序好的子序列,合并成一个最终有序的排序序列。

对于链表来说,不同于一般的数据序列,它找到中间节点之后,需要切断一下。因此用归并排序算法,去排链表的操作大概是这样:

  • 遍历链表,找到中间节点。
  • 找到中间节点后,切断
  • 分别再用归并排序,排左右子链表
  • 合并子链表

 C++核心代码

class Solution {
public:ListNode* sortList(ListNode* head) {if (!head || !head->next) return head;// 获取链表的中间节点ListNode* middle = getMiddle(head);//归并排序:分成两部分//前半部分链表以 head 为起点,到 middle 为终点,后半部分链表以 nextOfMiddle 为起点。ListNode* nextOfMiddle = middle->next;middle->next = nullptr;// 递归排序链表的左右两部分ListNode* left = sortList(head);ListNode* right = sortList(nextOfMiddle);// 合并排序后的链表return merge(left, right);}private:// 合并两个已排序的链表ListNode* merge(ListNode* l1, ListNode* l2) {ListNode dummy(0);ListNode* tail = &dummy;while (l1 && l2) {if (l1->val < l2->val) {tail->next = l1;l1 = l1->next;} else {tail->next = l2;l2 = l2->next;}tail = tail->next;}tail->next = l1 ? l1 : l2;return dummy.next;}// 获取链表的中间节点ListNode* getMiddle(ListNode* head) {if (!head) return head;ListNode* slow = head;ListNode* fast = head->next;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}return slow;}
};

相关文章:

代码练习12-排序链表

给你链表的头结点 head &#xff0c;请将其按 升序 排列并返回 排序后的链表 。 归并排序算法核心步骤 归并排序核心步骤如下&#xff1a; 把长度为n的要排序的序列&#xff0c;分成两个长度为n/2的子序列&#xff1b;对这两个子序列&#xff0c;分别采用归并排序&#xff1b…...

Linux 内核源码分析---套接字

套接字通信 ISO 设计一种参考模型&#xff0c;定义组成网络的各个层&#xff0c;该模型由7层组成&#xff0c;称为OSI&#xff08;开放 系统互连&#xff09;模型如下&#xff1a; 应用层&#xff1a;网络服务与最终用户的接口&#xff1b; 表示层&#xff1a;数据的表示、安…...

vscode配置xdebug断点调试详细教程

注&#xff1a;环境为本地windows开发环境&#xff0c;编辑器为vscode&#xff0c;PHP集成环境工具为EServer vscode安装扩展并配置 安装PHP Debug 扩展中搜索 PHP Debug 并安装&#xff1a; 配置PHP Debug 1、点击扩展设置 2、在设置中&#xff0c;点击 setting.json 3、编…...

【人工智能】Transformers之Pipeline(八):文生图/图生图(text-to-image/image-to-image)

目录 一、引言 二、文生图/图生图&#xff08;text-to-image/image-to-image&#xff09; 2.1 文生图 2.2 图生图 2.3 技术原理 2.3.1 Diffusion扩散模型原理 2.3.2 Stable Diffusion扩散模型原理 2.4 文生图实战 2.4.1 SDXL 1.0 2.4.2 SD 2.0 2.5 模型排名 三、总…...

AI Agent 工程师认证-学习笔记(1)——【单Agent】ModelScope-Agent

学习链接&#xff1a; 【单Agent】ModelScope-Agent学习指南https://datawhaler.feishu.cn/wiki/GhOLwvAPkiSWmokjUgqc1eGonDf 手把手Agent开发开源教程&#xff08;觉得不错的话可以star一下&#xff09;https://github.com/datawhalechina/agent-tutorial 动手学Agent应用…...

【Python机器学习】树回归——将CART算法用于回归

要对数据的复杂关系建模&#xff0c;可以借用树结构来帮助切分数据&#xff0c;如何实现数据的切分&#xff1f;怎样才能知道是否已经充分切分&#xff1f;这些问题的答案取决于叶节点的建模方式。回归树假设叶节点是常数值&#xff0c;这种策略认为数据中的复杂关系可以用树结…...

前端(HTML + CSS)小兔鲜儿项目(仿)

前言 这是一个简单的商城网站&#xff0c;代码部分为HTML CSS 和少量JS代码 项目总览 一、头部区域 头部的 购物车 和 手机 用的是 文字图标&#xff0c;所以效果可以和文字一样 购物车右上角用的是绝对定位 logo用的是 h1 标签&#xff0c;用来提高网站搜索排名 二、banne…...

【Rust光年纪】构建高效终端用户界面:Rust库全面解析

构建优雅终端应用&#xff1a;深度评析六大Rust库 前言 随着Rust语言的流行和应用场景的不断扩大&#xff0c;对于终端操作和用户界面构建的需求也日益增长。本文将介绍一些在Rust语言中常用的终端操作库和用户界面构建库&#xff0c;以及它们的核心功能、使用场景、安装与配…...

鼠标滑动选中表格部分数据列(vue指令)

文章目录 代码指令代码使用代码 代码 指令代码 // 获得鼠标移动的范围 function getMoveRange(startClientX, endClientX, startClientY, endClientY) {const _startClientX Math.min(startClientX, endClientX);const _endClientX Math.max(startClientX, endClientX);con…...

“5G+Windows”推动全场景数字化升级:美格智能5G智能模组SRM930成功运行Windows 11系统

操作系统作为连接用户与数字世界的桥梁&#xff0c;在数字化迅速发展的时代扮演着至关重要的角色&#xff0c;智能设备与操作系统的协同工作&#xff0c;成为推动现代生活和商业效率的关键力量。其中&#xff0c;Windows系统以其广泛的应用基础和强大的兼容性成为全球最广泛使用…...

c语言学习,isupper()函数分析

1&#xff1a;isupper() 函数说明&#xff1a; 检查参数c&#xff0c;是否为大写英文字母。 2&#xff1a;函数原型&#xff1a; int isupper(int c) 3&#xff1a;函数参数&#xff1a; 参数c&#xff0c;为检测整数 4&#xff1a;返回值&#xff1a; 参数c是大写英文字母&…...

Adnroid 数据存储:SharedPreferences详解【SharedPreferencesUtils,SharedPreferences的ANR】

目录 1&#xff09;SP是什么、如何使用&#xff0c;SPUtils 2&#xff09;SP的流程 3&#xff09;comit和apply 一、SP是什么&#xff0c;如何使用&#xff0c;SPUtils 1.1 SP是什么&#xff1f; SharedPreferences是Android平台提供的一种轻量级的数据存储方式&#xff0c;…...

Sentinel 规则持久化到 Nacos 实战

前言&#xff1a; 前面系列文章我们对 Sentinel 的作用及工作流程源码进行了分析&#xff0c;我们知道 Sentinel 的众多功能都是通过规则配置完成的&#xff0c;但是我们前面在演示的时候&#xff0c;发现 Sentinel 一重启&#xff0c;配置的规则就没有了&#xff0c;这是因为…...

服务器CPU天梯图2024年8月,含EYPC/至强及E3/E5

原文地址&#xff08;高清无水印原图/持续更新/含榜单出处链接&#xff09;&#xff1a; >>>服务器CPU天梯图<<< 本文提供的服务器CPU天梯图数据均采集自各大专业网站&#xff0c;榜单图片末尾会标准其来源&#xff08;挂太多链接有概率会被ban&#xff0c;…...

SpringBoot加载dll文件示例

1、将动态库放在resource文件目录下 2、编写相关加载逻辑 import lombok.extern.slf4j.Slf4j; import java.io.File; import java.io.IOException; import java.lang.reflect.Field; import java.util.HashMap;/*** Description: 加载动态库 .dll文件* author: Be.insighted* c…...

9.C基础_指针与数组

数组指针&#xff08;一维数组&#xff09; 数组指针就是" 数组的指针 "&#xff0c;它是一个指向数组首地址的指针变量。 1、数组名的含义 对于一维数组&#xff0c;数组名就是一个指针&#xff0c;指向数组的首地址。 基于如下代码进行分析&#xff1a; int a…...

C语言——结构体与共用体

C语言——结构体与共用体 结构体共用体 结构体 如果将复杂的复杂的数据类型组织成一个组合项&#xff0c;在一个组合项中包含若干个类型不同&#xff08;当然也可以相同&#xff09;的数据项。 C语言允许用户自己指定这样一种数据结构&#xff0c;它称为结构体。 结构体的语法…...

vs+qt项目转qt creator

1、转换方法 打开vs工程&#xff0c;右键项目&#xff0c;Qt->Create Base .pro File 后面默认OK 如果工程有include和lib路径需要配置&#xff0c;则转换后的工程&#xff0c;需要修改pro文件 2.修改pro文件 例如转换后的工程如下&#xff1a; 修改后 # ------------…...

微信小程序 checkbox 实现双向绑定以及特殊交互处理

wxml文件代码如下&#xff1a; <!--页面顶部 引入wxs文件--> <wxs module"tools" src"../../filter/tools.wxs"></wxs> ... <checkbox-group bindchange"checkboxChange"><label class"weui-cell weui-check__…...

我在高职教STM32——I2C通信之读写EEPROM(1)

大家好,我是老耿,高职青椒一枚,一直从事单片机、嵌入式、物联网等课程的教学。对于高职的学生层次,同行应该都懂的,老师在课堂上教学几乎是没什么成就感的。正是如此,才有了借助CSDN平台寻求认同感和成就感的想法。在这里,我准备陆续把自己花了很多心思设计的教学课件分…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...