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

牛客TOP101:单链表的排序

文章目录

  • 1. 题目描述
  • 2. 解题思路
  • 3. 代码实现

1. 题目描述

在这里插入图片描述

2. 解题思路

  按我们以往的排序算法来看,针对链表来说都是太不合适,因为很多都会出现指针前移后移,后移还好说,前移对于链表来说就太难了,而且大部分都是某一个位置和另一个离它很远的位置进行比较交换位置,这在链表中是不切实际的。
  但是其中的归并,非常的适合链表,相信大家也做过合并两个排序的链表和合并k个已排序的链表,其实针对于单个链表的排序,归并也是非常合适的,因为其底层其实是两个挨着的结点进行排序的。
  其原理就是先通过递归将一个链表分成一个一个单个的结点,然后两两进行比较、排序、连接,这是第一次排序,再往后就是具有两个结点的链表和另一个具有两个结点的链表进行排序,那么此时问题就是合并两个排序的链表了
  这样我们就完成了一个链表的排序。那么现在的问题就是如何分隔链表呢? 就是通过递归,在单次中,我们使用left,mid,right三个指针:
在这里插入图片描述
  left和mid一次走一步,right一次走两步,这样当right到最后一个结点时,mid就在中间,然后再让left->next指向nullptr,断开两个链表。这样再对左右两个链表递归下去,就完成了链表的分隔。当分隔成一个结点的时候,就会开始排序。
  在我八大排序的博客中的归并排序中,有详细的分隔过程,想了解的可以点击跳转。

3. 代码实现

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param head ListNode类 the head node* @return ListNode类*/ListNode* Merge(ListNode* head1, ListNode* head2){if(head1 == nullptr) return head2;if(head2 == nullptr) return head2;auto ret = new ListNode(-1);auto head = ret;while(head1 && head2){if(head1->val < head2->val){ret->next = head1;head1 = head1->next;}else {ret->next = head2;head2 = head2->next;}ret = ret->next;}if(head1) ret->next = head1;if(head2) ret->next = head2;return head->next;}ListNode* sortInList(ListNode* head) {if(head == nullptr || head->next == nullptr)return head;ListNode* left = head, *mid = head->next, *right = head->next;while(right && right->next){left = left->next;mid = mid->next;right = right->next->next;}left->next = nullptr;return Merge(sortInList(head), sortInList(mid));}
};

相关文章:

牛客TOP101:单链表的排序

文章目录 1. 题目描述2. 解题思路3. 代码实现 1. 题目描述 2. 解题思路 按我们以往的排序算法来看&#xff0c;针对链表来说都是太不合适&#xff0c;因为很多都会出现指针前移后移&#xff0c;后移还好说&#xff0c;前移对于链表来说就太难了&#xff0c;而且大部分都是某一个…...

数据可视化配色新工具,颜色盘多达2500+类

好看的配色,不仅能让图表突出主要信息,更能吸引读者,之前分享过很多配色工具,例如, 👉可视化配色工具:颜色盘多达3000+类,数万种颜色! 本次再分享一个配色工具pypalettes,颜色盘多达2500+类。 安装pypalettes pip install pypalettes pypalettes使用 第1步,挑选…...

SpringAI简单使用(本地模型+自定义知识库)

Ollama 简介 Ollama是一个开源的大型语言模型服务工具&#xff0c;它允许用户在本地机器上构建和运行语言模型&#xff0c;提供了一个简单易用的API来创建、运行和管理模型&#xff0c;同时还提供了丰富的预构建模型库&#xff0c;这些模型可以轻松地应用在多种应用场景中。O…...

为什么要从C语言开始编程

在开始前刚好我有一些资料&#xff0c;是我根据网友给的问题精心整理了一份「C语言的资料从专业入门到高级教程」&#xff0c; 点个关注在评论区回复“888”之后私信回复“888”&#xff0c;全部无偿共享给大家&#xff01;&#xff01;&#xff01;很多小伙伴在入门编程时。都…...

[数据集][目标检测]导盲犬拐杖检测数据集VOC+YOLO格式4635张2类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;4635 标注数量(xml文件个数)&#xff1a;4635 标注数量(txt文件个数)&#xff1a;4635 标注…...

数据结构(稀疏数组)

简介 稀疏数组是一种数据结构&#xff0c;用于有效地存储和处理那些大多数元素都是零或者重复值的数组。在稀疏数组中&#xff0c;只有非零或非重复的元素会被存储&#xff0c;从而节省内存空间。 案例引入 假如想把下面这张表存入文件&#xff0c;我们会怎么做&#xff1f;…...

python 爬虫技术 第02节 基础复习

Python基础复习 Python 是一种高级、通用、解释型的编程语言&#xff0c;以其简洁的语法和强大的功能在数据科学、Web 开发、自动化脚本编写、机器学习等领域广泛使用。下面是一些 Python 基础概念的复习&#xff1a; 1. 数据类型 Python 支持多种内置数据类型&#xff0c;包…...

数据结构-C语言-排序(3)

代码位置&#xff1a;test-c-2024: 对C语言习题代码的练习 (gitee.com) 一、前言&#xff1a; 1.1-排序定义&#xff1a; 排序就是将一组杂乱无章的数据按照一定的规律&#xff08;升序或降序&#xff09;组织起来。(注&#xff1a;我们这里的排序采用的都为升序) 1.2-排序分…...

【分布式事务】怎么解决分布式场景下数据一致性问题

分布式事务的由来 拿充值订单举个栗子吧&#xff0c;假设&#xff1a;原本订单模块和账户模块是放在一起的&#xff0c;现在需要做服务拆分&#xff0c;拆分成订单服务&#xff0c;账户余额服务。原本收到充值回调后&#xff0c;可以将修改订单状态和扣减余额放在一个mysql事务…...

C# 中的委托

委托的概念 在C#中&#xff0c;委托是一种引用类型&#xff0c;它表示对方法的引用&#xff0c;即委托就是一种用来指向一个方法的引用类型变量。委托的声明类似于方法签名&#xff0c;但是关键字是delegate。下面是一个委托的声明和使用的例子&#xff1a; // 声明一个委托 p…...

通过docker构建基于LNMP的WordPress项目

目录 1.准备nginx 2.准备mysql 3.准备php 4.构建各镜像 5.运行wordpress 1、项目环境&#xff1a; 1.1 &#xff08;1&#xff09;公司在实际的生产环境中&#xff0c;需要使用Docker 技术在一台主机上创建LNMP服务并运行Wordpress网站平台。然后对此服务进行相关的性能…...

2024新版IntelliJ IDEA修改包名 全网最简单最粗暴的方法

问题再现 我们在网上淘一些后端框架 又或者是开源的项目 如果要变成自己的 难免会去改包名 即把com.后面的内容改成自己自定义的 第一次我们直接用网络上的方法 shift F6 快捷键 可以修改包名 出现以下情况 进行修改 我们发现失败了 并没有像预计的一样直接把包名修…...

C#中处理Socket粘包

在C#中使用Socket进行网络通信时&#xff0c;粘包问题是常见的。粘包问题通常发生在TCP协议中&#xff0c;因为TCP是流式协议&#xff0c;数据可能会被分割成多个包发送&#xff0c;也可能多个小包会被合并成一个大包接收。 处理粘包问题的常见方法是使用消息分隔符或消息长度…...

7.19IO

思维导图 第一题&#xff1a;测试错误检查锁和递归锁是否会造成死锁状态 #include <stdio.h> #include <string.h> #include <stdlib.h> #include <unistd.h> #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #i…...

【Vue】深入了解 Axios 在 Vue 中的使用:从基本操作到高级用法的全面指南

文章目录 一、Axios 简介与安装1. 什么是 Axios&#xff1f;2. 安装 Axios 二、在 Vue 组件中使用 Axios1. 发送 GET 请求2. 发送 POST 请求 三、Axios 拦截器1. 请求拦截器2. 响应拦截器 四、错误处理五、与 Vuex 结合使用1. 在 Vuex 中定义 actions2. 在组件中调用 Vuex acti…...

【Qt】窗口

文章目录 QMainWindow菜单栏工具栏状态栏浮动窗口对话框自定义对话框Qt内置对话框QMessageBox QMainWindow Qt中的主窗口以QMainWindow表示&#xff0c;其总体结构如下&#xff1a; 菜单栏 菜单栏MenuBar&#xff0c;可包含多个菜单Menu&#xff0c;每个菜单也可以包含多个菜…...

代码随想录训练营【贪心算法篇】

贪心 注&#xff1a;本文代码来自于代码随想录 贪心算法一般分为如下四步&#xff1a; 将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解 这个四步其实过于理论化了&#xff0c;我们平时在做贪心类的题目 很难去按照这四步…...

Spark中的JOIN机制

Spark中的JOIN机制 1、Hash Join概述2、影响JOIN的因素3、Spark中的JOIN机制3.1、Shuffle Hash Join3.2、Broadcast Hash Join3.3、Sort Merge Join3.4、Cartesian Product Join3.5、Broadcast Nested Loop Join4、Spark中的JOIN策略5、Spark JOIN机制与策略总结5.1、Spark中的…...

WebRTC QOS方法十三.1(TimestampExtrapolator接收时间预估)

一、背景介绍 虽然我们可通过时间戳的差值和采样率计算出发送端视频帧的发送节奏&#xff0c;但是由于网络延迟、抖动、丢包&#xff0c;仅知道视频发送端的发送节奏是明显不够的。我们还需要评估出视频接收端的视频帧的接收节奏&#xff0c;然后进行适当平滑&#xff0c;保证…...

深入了解 GCC

GCC&#xff0c;全称 GNU Compiler Collection&#xff0c;是 GNU 项目的一部分&#xff0c;是一个功能强大且广泛使用的编译器套件。它支持多种编程语言&#xff0c;包括 C、C、Fortran、Java、Ada 和 Go。GCC 具有高度的可移植性&#xff0c;几乎可以在所有现代计算机体系结构…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向

在人工智能技术呈指数级发展的当下&#xff0c;大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性&#xff0c;吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型&#xff0c;成为释放其巨大潜力的关键所在&…...

CentOS 7.9安装Nginx1.24.0时报 checking for LuaJIT 2.x ... not found

Nginx1.24编译时&#xff0c;报LuaJIT2.x错误&#xff0c; configuring additional modules adding module in /www/server/nginx/src/ngx_devel_kit ngx_devel_kit was configured adding module in /www/server/nginx/src/lua_nginx_module checking for LuaJIT 2.x ... not…...

LeetCode - 148. 排序链表

目录 题目 思路 基本情况检查 复杂度分析 执行示例 读者可能出的错误 正确的写法 题目 148. 排序链表 - 力扣&#xff08;LeetCode&#xff09; 思路 链表归并排序采用"分治"的策略&#xff0c;主要分为三个步骤&#xff1a; 分割&#xff1a;将链表从中间…...

运动控制--BLDC电机

一、电机的分类 按照供电电源 1.直流电机 1.1 有刷直流电机(BDC) 通过电刷与换向器实现电流方向切换&#xff0c;典型应用于电动工具、玩具等 1.2 无刷直流电机&#xff08;BLDC&#xff09; 电子换向替代机械电刷&#xff0c;具有高可靠性&#xff0c;常用于无人机、高端家电…...