牛客热题:单链表排序

📟作者主页:慢热的陕西人

🌴专栏链接:力扣刷题日记

📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言

在这里插入图片描述

文章目录

  • 牛客热题:单链表排序
    • 题目链接
    • 方法一:用数组排序再赋值回来
      • 思路
      • 代码
      • 复杂度
    • 方法二:归并排序
      • 思路
      • 代码
      • 复杂度

牛客热题:单链表排序

题目链接

单链表的排序_牛客题霸_牛客网 (nowcoder.com)

方法一:用数组排序再赋值回来

思路

  • 用数组先将链表中的值存储起来
  • 对数组进行排序
  • 将数组的值赋值给链表

代码

    ListNode* sortInList(ListNode* head) {vector<int> v;ListNode* cur = head;while(cur != nullptr){v.push_back(cur->val);cur = cur->next;}sort(v.begin(), v.end());cur = head;for(auto & vv : v){cur->val = vv;cur = cur->next;}return head;}

复杂度

时间复杂度:O( N l o g N NlogN NlogN),用了c++原生的sort,底层是快排。

空间复杂度;O(N),借用了额外的数组空间

方法二:归并排序

思路

  • 先将原先的链表,对半分开直到不能再分(单个节点的情况)
  • 然后再将他们按照有序的方式合并

分开:

  • 快慢指针的思路,快指针一步走两个节点,慢指针一步走一个节点
  • 当快指针到达链表结尾的时候,那么这时候,慢指针恰好就在链表的中间位置
  • 我们从这块将两个链表分开就好

合并:

  • 创建一个哨兵位
  • 遍历比较排序好的左右单链表区间
  • 并逐个比较,尾插到哨兵位

代码

    ListNode* sortInList(ListNode* head) {if(head == nullptr || head->next == nullptr) return head;//快慢指针寻找链表的中点ListNode* fast = head->next;ListNode* slow = head;while(fast != nullptr && fast->next != nullptr){slow = slow->next;fast = fast->next->next;}//将链表从中间分开ListNode* temp = slow->next;slow->next = nullptr;//递归左右两边进行排序ListNode* left = sortInList(head);ListNode* right = sortInList(temp);//创建新的链表,带有哨兵位ListNode* h = new ListNode(0);ListNode* res = h;        //合并left和right两个链表while(left != nullptr && right != nullptr){if(left->val < right->val){h->next = left;left = left->next;}else {h->next = right;right = right->next;}h = h->next;}//最后查看left和right哪个还有剩余未添加的节点h->next = left == nullptr ? right : left;return res->next; }

复杂度

时间复杂度:O( N l o g N Nlog N NlogN),利用归并排序的思路实现。

空间复杂度:O(1),借用了常数个额外的空间。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/320376.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Windows php 安装 Memcached扩展、php缺失 Memcached扩展、Class ‘Memcached‘ not found

在Windows系统下如何安装 php Memcached 扩展 下载dll文件 pecl地址&#xff1a;https://pecl.php.net/package/memcached 根据版本进行选择 &#xff1a; 解压下载的文件后得到了这么样的文件结构&#xff1a; 配置 移动dll文件到相应文件位置 重点&#xff1a; libme…

jdk环境安装

jdk安装 创建软件安装的目录 mkdir -p /bigdata/{soft,server} /bigdata/soft 安装文件的存放目录 /bigdata/server 软件安装的目录 把安装的软件上传到/bigdata/soft 目录 解压到指定目录 -C :指定解压到指定目录 tar -zxvf /bigdata/soft/jdk-8u241-linux-x64.tar.gz -C /b…

【Osek网络管理测试】[TG3_TC3]tSleepRequestMin_L

&#x1f64b;‍♂️ 【Osek网络管理测试】系列&#x1f481;‍♂️点击跳转 文章目录 1.环境搭建2.测试目的3.测试步骤4.预期结果5.测试结果 1.环境搭建 硬件&#xff1a;VN1630 软件&#xff1a;CANoe 2.测试目的 验证DUT进入NMLimpHome状态后请求睡眠的最短时间是否正确…

Android --- 消息机制与异步任务

在Android中&#xff0c;只有在UIThread(主线程)中才能直接更新界面&#xff0c; 在Android中&#xff0c;长时间的工作联网都需要在workThread(分线程)中执行 在分线程中获取服务器数据后&#xff0c;需要立即到主线程中去更新UI来显示数据&#xff0c; 所以&#xff0c;如…

NI CRIO 9045 LABVIEW2020

1.labview工程如果要访问CRIO&#xff0c;需要设置以下&#xff0c;否则在项目中连接失败。 2.项目中如果要传文件&#xff0c;需要安装WebDEV 3.使用WebDAV将文件传输到实时(RT)目标 https://knowledge.ni.com/KnowledgeArticleDetails?idkA03q000000YGytCAG&lzh-CN

Mars3d实现用一个button控制一个map.control的显示与隐藏

原生js,想做一个button,控制比如compass的显示与隐藏 点一下显示 再次单击的时候就隐藏掉 写了一个function控制显示隐藏 function addCompass(){ if(compass.showtrue) { compass.showfalse; } else{ compass.showtrue; } } 功能示例(Vue版) | Mars3D三维可视化平台 | 火星…

深入了解C/C++的内存区域划分

&#x1f525;个人主页&#xff1a;北辰水墨 &#x1f525;专栏&#xff1a;C学习仓 本节我们来讲解C/C的内存区域划分&#xff0c;文末会附加一道题目来检验成果&#xff08;有参考答案&#xff09; 一、大体有哪些区域&#xff1f;分别存放什么变量开辟的空间&#xff1f; …

【微服务】网关(详细知识以及登录验证)

微服务网关 网关网关路由快速入门路由属性 路由断言网关登录校验自定义过滤器实现登录校验网关传递用户OpenFeign传递用户 网关 网络的关口&#xff0c;负责请求的路由&#xff0c;转发&#xff0c;身份校验 当我们把一个单体项目分成多个微服务并部署在多台服务器中&#xff…

Redis__数据类型

文章目录 &#x1f60a; 作者&#xff1a;Lion J &#x1f496; 主页&#xff1a; https://blog.csdn.net/weixin_69252724 &#x1f389; 主题&#xff1a;Redis__数据类型 ⏱️ 创作时间&#xff1a;2024年04月28日 ———————————————— 这里写目录标题 文…

大模型争霸的下一站:不仅是超越GPT-4,更是寻求模型之间的平衡应用

文 | 智能相对论 作者 | 沈浪 知名科学杂志《Nature》发表了一篇关于大模型规模参数大小争议的文章《In Al, is bigger always better?》——AI大模型&#xff0c;越大越好吗&#xff1f;随着大模型应用走向实践&#xff0c;这一问题不可避免地成为了当前AI行业发展的焦点与…

迅雷永久破解

链接&#xff1a;https://pan.baidu.com/s/1ZGb1ljTPPG3NFsI8ghhWbA?pwdok7s 下载后解压 以管理员身份运行绿化.bat&#xff0c;会自动生成快捷方式&#xff0c;如果没有可以在program中运行Thunder.exe

【python】条件语句与循环语句

目录 一.条件语句 1.定义 2.条件语句格式 &#xff08;1&#xff09;if &#xff08;2&#xff09;if-else &#xff08;3&#xff09;elif功能 &#xff08;4&#xff09;if嵌套使用 3.猜拳游戏 二.循环语句 1. while循环 2.while嵌套 3.for循环 4.break和conti…

AI图书推荐:AI在语言学习教育领域的应用和挑战

这本书《AI在语言学习教育领域的应用和挑战》&#xff08;AI in Language Teaching, Learning, and Assessment&#xff09;由Fang Pan编辑&#xff0c;出版于IGI Global&#xff0c;主要探讨了人工智能&#xff08;AI&#xff09;在语言教育领域的应用、挑战以及潜在的益处。 …

JS基础:JS语法规范详解(最全!)

你好&#xff0c;我是云桃桃。 一个希望帮助更多朋友快速入门 WEB 前端的程序媛。 云桃桃-大专生&#xff0c;一枚程序媛&#xff0c;感谢关注。回复 “前端基础题”&#xff0c;可免费获得前端基础 100 题汇总&#xff0c;回复 “前端基础路线”&#xff0c;可获取完整web基础…

C++:自增运算符(++)重载

自增运算符&#xff08;&#xff09;分为前置自增和后置自增&#xff0c;它们两者主要的区别是&#xff1a;返回的值不同&#xff0c;以及执行自增操作的顺序不同。 前置自增运算符 &#xff1a; 前置自增运算符首先将操作数加1&#xff0c;然后返回自增后的值。 这意味着如果…

CNN笔记详解

CNN(卷积神经网络) 计算机视觉&#xff0c;当你们听到这一概念的是否好奇计算机到底是怎样知道这个图片是什么的呢&#xff1f;为此提出了卷积神经网络&#xff0c;通过卷积神经网络&#xff0c;计算机就可以识别出图片中的特征&#xff0c;从而识别出图片中的物体。看到这里充…

盘一盘接口测试的那些痛点,你现在会解决了吗

前言 说到接口测试&#xff0c;想必大家一定不会陌生。接口测试就是测试系统组件间&#xff0c;接口对接是否顺畅的一种测试。包括测试数据能否交换、能否传递、能否正常控制管理过程&#xff0c;以及系统间的相互逻辑依赖关系&#xff0c;等等。 由于接口测试主要是检测系统…

2024网络安全面试问题宝典(4万字)

2024网络安全厂商面试问题宝典(4万字) 目录 评分标准网络基础问题 TCP建立连接要进行3次握手&#xff08;syn-syn&#xff0c;ack-ack&#xff09;&#xff0c;而断开连接要进行4次&#xff08;fin-ack-fin-ack&#xff09;TCP&#xff0c;UDP区别&#xff1a;安全常用的协议…

数据库基础--MySQL多表查询之联表查询

联表查询 定义&#xff1a;多张表联合在一起查询&#xff0c;例如学生信息与学生班级表、部门与员工表 创建两张表&#xff0c;主表与从表 CREATE TABLE TestMain(id INT Not NULL AUTO_INCREMENT,nameVARCHAR(10),introduction VARCHAR(255),PRIMARY KEY(id) ); CREATE TAB…

自动驾驶主流芯片及平台架构(二)特斯拉自动驾驶芯片平台介绍

早期 对外采购mobileye EyeQ3 芯片摄像头半集成方案&#xff0c;主要是为了满足快速量产需求&#xff0c;且受制于研发资金不足限制&#xff1b; 中期 采用高算力NVIDIA 芯片平台其他摄像头供应商的特斯拉内部集成方案&#xff0c;mobileye开发节奏无法紧跟特斯拉需求&#xff…