LeetCode Hot100 排序链表

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

示例 1:

输入:head = [4,2,1,3]
输出:[1,2,3,4]

示例 2:

输入:head = [-1,5,3,4,0]
输出:[-1,0,3,4,5]

示例 3:

输入:head = []
输出:[]

归并排序

思路

        题目要求O(nlogn)时间复杂度和O(1)空间复杂度,使用归并排序而非是快速排序,归并排序比快排稳定。把链表分割成节点,再合并

代码 

class Solution {
public:ListNode* merge(ListNode* list1, ListNode* list2){ListNode* mergelist = new ListNode(0); ListNode* node = mergelist;while(list1 != nullptr && list2 != nullptr){if(list1->val > list2->val){node->next = list2;list2 = list2->next;}else{node->next = list1;list1 = list1->next;}node = node->next;}if(list1 != nullptr)node->next = list1;else if(list2 != nullptr)node->next = list2;return mergelist->next;}ListNode* sortList(ListNode* head) {     if(head == nullptr || head->next == nullptr)return head;int listlen = 0;ListNode* res = new ListNode(0, head);while(head != nullptr){head = head->next;++listlen;}for(int i=1; i<listlen; i*=2){ListNode* tmp = res->next;ListNode* tail = res;while(tmp != nullptr){ListNode* left = tmp;for(int j=1; j<i && tmp->next!=nullptr; ++j)tmp = tmp->next;ListNode* right = tmp->next;tmp->next = nullptr;tmp = right;for(int j=1; j<i && tmp!=nullptr && tmp->next!=nullptr; ++j)tmp = tmp->next;ListNode* next = nullptr;if(tmp != nullptr){next = tmp->next;tmp->next = nullptr;}tail->next = merge(left, right);while(tail->next != nullptr)tail = tail->next;tmp = next;}}ListNode* secondhead = res->next;delete res;return secondhead;}
};

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

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

相关文章

工程技术人员职称专业一览表,赶紧收藏!有助评职称、落户

现在很多地区为了引进人才&#xff0c;都会对各类获得中级或高级职称的人才提供一系列优惠政策&#xff0c;比如人才补贴、职称入户等等。 下面小编就来为大家介绍一下中级职称专业一览表&#xff0c;告诉你能以考代评的几个考试&#xff0c;需要评职称、落户的快看过来&#…

【秋招突围】2024届秋招-京东笔试题-第二套

🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 编程一对一辅导 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍭 本次给大家…

PXE:Kickstart自动化安装Linux系统

PXE&#xff1a;工作在 Client/Server模式&#xff0c;允许客户机通过网络从远程服务器下载引导镜像&#xff0c;并加载安装文件或者整个操作系统。 运行 PXE协议需要设置&#xff1a;DHCP服务器和TFTP服务器。DHCP服务器用来给 PXE client&#xff08;将要安装系统的主机&…

【C++二分查找 决策包容性】1300. 转变数组后最接近目标值的数组和

本文涉及的基础知识点 C二分查找 决策包容性 LeetCode1300. 转变数组后最接近目标值的数组和 给你一个整数数组 arr 和一个目标值 target &#xff0c;请你返回一个整数 value &#xff0c;使得将数组中所有大于 value 的值变成 value 后&#xff0c;数组的和最接近 target …

element plus el-select修改后缀图标

使用 element plus 提供的api 默认为&#xff1a; 修改后为&#xff1a; 方法&#xff1a; <el-select v-model"value" placeholder"Select" size"large" style"width: 120px;":teleported"false" :suffix-icon"…

香港电讯为知名地产商构建安全稳定可靠的企业组网

客户背景 客户公司的总部位于香港&#xff0c;专注于房地产、酒店、基础设施及服务、商场等业务。经过多年沉淀&#xff0c;其内地业务不断壮大&#xff0c;拓展至各个地区并覆盖多个城市&#xff0c;原有的网络架构已无法满足客户的业务扩张需求。 客户需求 解决网络速度和稳…

python-约瑟夫环(赛氪OJ)

[题目描述] n 个人&#xff08; 0,1,2,3,4...n−1 &#xff09;&#xff0c;围成一圈&#xff0c;从编号为 k 的人开始报数&#xff0c;报数报到 m 的人出队。 下次从出队的人之后开始重新报数&#xff0c;循环往复&#xff0c;当队伍中只剩最后一个人的时候&#xff0c;那个人…

C++从入门到起飞之——深浅拷贝string类补充 全方位剖析!

​ &#x1f308;个人主页&#xff1a;秋风起&#xff0c;再归来~&#x1f525;系列专栏&#xff1a;C从入门到起飞 &#x1f516;克心守己&#xff0c;律己则安 目录 1、浅拷贝 2、深拷贝 3、现代版写法的拷贝构造和赋值重载 4、再探swap! 5、写实拷贝&#xff…

面试官:怎样设计一个分布式任务调度平台?

大家好&#xff0c;我是君哥。 在工作中&#xff0c;批量任务调度的需求经常会遇到&#xff0c;比如下面的几个场景&#xff1a; 数据迁移&#xff1a;从数据库 A 批量读取数据&#xff0c;加工后把数据写入数据库 B&#xff1b; 消息通知&#xff1a;运营商批量给客户发送短…

同态加密和SEAL库的介绍(二)BFV 基础方案实现

写在前面&#xff1a; 本篇具体讲解如何使用 BFV 加密方案对加密的整数进行简单的计算&#xff08;一个多项式评估&#xff09;&#xff0c;来源是官方提供的示例。BFV 是比较常见的方案&#xff0c;在很多大模型推理的时候&#xff0c;都是将浮点数的权重和输入变换成…

MongoDB学习笔记(三)

使用Python操作MongoDB: 使用管理员用户&#xff1a;

web基础与http协议与配置

目录 一、web基础 1.1 DNS与域名&#xff08;详解看前面章节&#xff09; 1.2 网页的概念&#xff08;HTTP/HTTPS&#xff09; 1.2.1 基本概念 1.2.2 HTML文档结构(了解) 1.2.3 web相关重点 1.2.4 静态资源和动态资源 二、http协议 2.1 概述 2.2 cookie和session&…

云原生真机实验

基于Proxmox VE构建中小企业云计算平台 首先Proxmox VE是什么&#xff1f;能用来做什么&#xff1f; Proxmox VE是一个完整的企业虚拟化开源平台。借助内置的 Web 界面&#xff0c;可以在单个解决方案上轻松管理 VM(开虚拟机的) 和容器、软件定义的存储和网络、高可用性群集以…

STM32开发之移植FreeRtos

一、新建STM32工程项目 &#xff08;1&#xff09;打开keil新建工程文件夹 &#xff08;2&#xff09;选择芯片型号 接下来会弹出来一个新建工程的小助手&#xff0c;我们关闭就好&#xff0c;接下来我们的工程就创建好了&#xff0c;但是工程还是空的 二、添加STM32的相关固件…

搭建 Web 群集Haproxy

案例概述 Haproxy 是目前比较流行的一种群集调度工具&#xff0c;同类群集调度工具有很多&#xff0c;如 LVS 和Nginx。相比较而言&#xff0c;LVS 性能最好&#xff0c;但是搭建相对复杂;Nginx 的upstream模块支持群集功能&#xff0c;但是对群集节点健康检查功能不强&#xf…

【C++】模版详解

1、概念 C模版分两类&#xff1a;函数模版和类模版 1&#xff09;函数模板的格式 template <class 形参名&#xff0c;class 形参名&#xff0c;......> 返回类型 函数名(参数列表) {函数体 }例如&#xff1a; template <class T> void swap(T& a, T& b…

机器人主板维修|ABB机械手主板元器件故障

【ABB机器人电路板故障原因诊断】 针对上述故障现象&#xff0c;我们需要对ABB机器人IO板进行详细的故障诊断。以下是一些可能的故障原因&#xff1a; 1. 元器件老化或损坏&#xff1a;ABB机械手安全面板上的元器件在长期使用过程中可能出现老化、损坏或接触不良等问题&#xf…

Unity 使用字符串更改Text指定文字颜色、大小、换行、透明

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、使用字符串改变文字属性的方法&#xff08;一&#xff09;修改颜色&#xff08;二&#xff09;修改大小&#xff08;三&#xff09;换行&#xff08;四&…

NC 矩阵的最小路径和

系列文章目录 文章目录 系列文章目录前言 前言 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站&#xff0c;这篇文章男女通用&#xff0c;看懂了就去分享给你的码吧。 描述 给定一个 n *…

【漏洞复现】某赛通数据泄露防护(DLP)系统 NetSecConfigAjax SQL注入漏洞

0x01 产品简介 某赛通新一代数据泄露防护系统&#xff08;简称 DLP&#xff09;&#xff0c;以服务企事业单位进行数据资产梳理、数据安全防护为目标。系统采用平台化管理&#xff0c;将终端DLP、网络DLP、邮件DLP、存储扫描DLP、API 接口DLP 进行统一管理&#xff0c;模块化控…