当前位置: 首页 > 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平台寻求认同感和成就感的想法。在这里,我准备陆续把自己花了很多心思设计的教学课件分…...

网络编程(Modbus进阶)

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

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

前端中slice和splic的区别

1. slice slice 用于从数组中提取一部分元素&#xff0c;返回一个新的数组。 特点&#xff1a; 不修改原数组&#xff1a;slice 不会改变原数组&#xff0c;而是返回一个新的数组。提取数组的部分&#xff1a;slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...