排序链表--字节跳动
少年的书桌上没有虚度的光阴
题目描述
请你对链表进行排序
思路分析
-
核心思想:归并排序
有三个部分
链表排序实现
1. merge 函数
21.见 合并两个有序链表,
-
首先创建一个虚拟头节点
newhead,并使用指针tail来构建合并后的链表。 -
通过循环比较
list1和list2节点的值,将较小值的节点连接到tail后面,并相应地移动指针。 -
当其中一个链表遍历完后,将另一个链表的剩余部分直接连接到
tail后面。 -
最后返回虚拟头节点的下一个节点,即合并后链表的头节点。
2. findMiddle 函数
该函数用于寻找链表的中间节点,采用快慢指针的方法:
-
fast指针每次移动两步,slow指针每次移动一步。 -
当
fast指针到达链表末尾时,slow指针就指向链表的中间节点。
3. sortList 函数
这是核心的排序函数,使用归并排序算法对链表进行排序:
-
首先判断链表是否为空或只有一个节点,如果是则直接返回该链表。
-
调用
findMiddle函数找到链表的中间节点,将链表分成左右两部分。 -
递归地对左右两部分链表分别调用
sortList函数进行排序。 -
最后调用
merge函数将两个有序的子链表合并成一个有序链表。
完整代码
class Solution {
public:// 合并两个有序链表ListNode* merge(ListNode* list1, ListNode* list2) {auto newhead = new ListNode(0); // 使用明确的类型名称auto tail = newhead;while (list1 && list2) {if (list1->val < list2->val) {tail->next = list1;list1 = list1->next;} else {tail->next = list2;list2 = list2->next;}tail = tail->next;}tail->next = list1 ? list1 : list2; // 处理剩余部分return newhead->next;}// 寻找中间节点ListNode* findMiddle(ListNode* head) {ListNode* fast = head;ListNode* slow = head;while (fast->next && fast->next->next) {fast = fast->next->next;slow = slow->next;}return slow;}// 归并排序链表ListNode* sortList(ListNode* head) {if (head==NULL ||head->next==NULL) return head; // 检查链表长度// 找到链表的中间节点ListNode* mid = findMiddle(head);ListNode* right = mid->next;mid->next = nullptr; // 切分链表// 递归地对左右两部分进行排序ListNode* l = sortList(head);ListNode* r = sortList(right);// 合并两个有序链表return merge(l, r);}
}
};
复杂度分析
-
时间复杂度: O(nlogn)
-
空间复杂度: O(logn)
相关文章:
排序链表--字节跳动
少年的书桌上没有虚度的光阴 题目描述 请你对链表进行排序 思路分析 核心思想:归并排序 有三个部分 链表排序实现 1. merge 函数 21.见 合并两个有序链表, 首先创建一个虚拟头节点 newhead,并使用指针 tail 来构建合并后的链表。 通过…...
Python爬虫-批量爬取股票数据猫各股票代码
前言 本文是该专栏的第47篇,后面会持续分享python爬虫干货知识,记得关注。 本文笔者以股票数据猫为例子,基于Python爬虫,批量获取各股票代码数据。 具体实现思路和详细逻辑,笔者将在正文结合完整代码进行详细介绍。废话不多说,下面跟着笔者直接往下看正文详细内容。(附…...
打开Firefox自动打开hao360.hjttif.com标签解决方案
现象 打开Firefox自动打开hao360.hjttif.com标签,同时用户自己设置的主页也会在一个新标签打开。点击hjttif这个标签,就会跳转到hao.360.com 打开Edge不会出现上述现象。搜遍全网都找不到解决方法。博客园上有一篇文章2025-02-14.防流氓软件篡改主页提到…...
【爬虫基础】第一部分 网络通讯-编程 P3/3
上节内容回顾:【爬虫基础】第一部分 网络通讯 P1/3-CSDN博客 【爬虫基础】第一部分 网络通讯-Socket套接字 P2/3-CSDN博客 相关文档,希望互相学习,共同进步 风123456789~-CSDN博客 前言 1.知识点碎片化:每个网站实现…...
Ubuntu 下 nginx-1.24.0 源码分析 - ngx_atoi 函数
ngx_atoi 声明在 src/core/ngx_string.h ngx_int_t ngx_atoi(u_char *line, size_t n); 定义在 src/core/ngx_string.c ngx_int_t ngx_atoi(u_char *line, size_t n) {ngx_int_t value, cutoff, cutlim;if (n 0) {return NGX_ERROR;}cutoff NGX_MAX_INT_T_VALUE / 10;cutlim…...
PG:ERROR: cannot freeze committed xmax
目录 原因**问题原因****PostgreSQL 底层逻辑** 解决方案1**问题分析****排查步骤****1. 检查长时间运行的事务****2. 检查未提交的事务****3. 检查 autovacuum 配置****4. 检查事务 ID 使用情况****5. 检查表的 relfrozenxid** **解决方法****1. 手动运行 VACUUM FREEZE****2.…...
《论软件的可靠性评价》审题技巧 - 系统架构设计师
论软件的可靠性评价写作框架 一、考点概述 软件可靠性评价作为软件可靠性活动的关键环节,是确保软件质量、提升用户体验的重要手段。本题主要考察以下几个方面的内容: 首先,本题要求考生理解并掌握软件可靠性评价的基本概念及其在软件开发…...
【项目设计】自主HTTP服务器
目录 项目介绍 网络协议栈介绍 协议分层 数据的封装与分用 HTTP相关知识介绍 HTTP的特点 URL格式 URI、URL、URN HTTP的协议格式 HTTP响应协议格式 HTTP的请求方法 HTTP的状态码 HTTP常见的Header CGI机制介绍 CGI机制的概念 CGI机制的实现步骤 CGI机制的意义 …...
Linux操作系统:基于Linux的个人Web服务器搭建与自动化运维实践
基于Linux的个人Web服务器搭建与自动化运维实践 摘要 在互联网的海洋中,每个人都想拥有一艘属于自己的小船——一个个人Web服务器。Linux作为开源界的“老大哥”,无疑是搭建Web服务器的最佳选择。本文通过幽默风趣的方式,详细介绍了在Linux…...
[创业之路-321]:创新开拓思维和经营管理思维的比较
目录 一、概述 1.1、定义与内涵 1、创新开拓思维: 2、经营管理思维: 1.2、特点与优势 1、创新开拓思维的特点与优势: 2、经营管理思维的特点与优势: 3、应用场景与限制 4、总结 二、创新开拓思维与经营管理思维…...
vivado修改下载器下载速率
Error Launching Program X Error while launching program: fpga configuration failed. DONE PIN is not HIGH 原因是下载器速度太快了。先从任务管理器中关闭hw_server.exe试一下,要是不行就按下面三种方法解决。 第一种方法可以不用修改下载速度,直接先从vivado中将bit流…...
运维基线方案说明
1. 总体思路 建立运维基线的核心目标是保障系统稳定性、提升安全性、及时响应异常事件并不断优化系统性能。初创公司资源有限,方案应尽可能简单、易用,同时具备一定的自动化和标准化能力。建议从以下几个层面入手: 标准化文档:制…...
pycharm中配置PyQt6详细教程
PyQt6 是 Qt 框架的 Python 绑定库,基于 Qt 6 开发,专为创建跨平台图形用户界面(GUI)应用程序设计。 本章教程,主要记录在pycharm中配置使用PyQt6的流程。 一、安装基础环境 在此之前,你需要提前安装好Python解释器,推荐使用anaconda创建虚拟环境。 conda create -n pyt…...
大湾区经济网报道:2025春运收官 全国跨区流动90亿,大湾区12亿人次
(原标题:2025年春运收官:全国跨区流动超90亿人次 大湾区贡献12亿人次) 大湾区经济网2月23日电(记者 余芳)2025年春运昨日(2月22日)正式结束,全国跨区域人员流动量达90.2…...
Docker用户的困境:免费项目的减少与成本的增加
摘要 在生产环境中,Docker用户正面临新的挑战:免费项目逐渐减少,收费服务成为主流趋势。表面上免费的选项,由于缺乏必要的支持和及时更新,反而可能导致更高的隐性成本。对于依赖Docker进行开发和部署的企业而言&#x…...
1.4 嵌入式系统的软件
嵌入式系统的开发流程中,硬件和固件设计完成后,嵌入式软件承担起实现功能、用户交互、系统集成和性能优化等任务;嵌入式系统软件分为设备驱动、操作系统和应用程序三个层面。 因此嵌入式系统软件开发工程师通常分为三类:嵌入式系统…...
PHP2(WEB)
##解题思路 打开页面什么线索都没有,目录扫描只是扫出来一个index.php,而源代码没有东西,且/robots.txt是不允许访问的 于是一番查询后发现,有个index.phps的文件路径,里头写着一段php的逻辑,对url的id参数…...
【精调】LLaMA-Factory 快速开始1: Meta-Llama-3.1-8B-Instruct
llamafactory-cli train examples/train_lora/llama3_lora_sft.yaml llamafactory-cli chat examples/inference/llama3_lora_sft.yaml llamafactory-cli export examples/merge_lora/llama3_lora_sft.yaml模型下载 git clone https://www.modelscope.cn/LLM-Research/Meta-Lla…...
一、计算机等级考试——题库
(1)选择题 (2)基本操作题 (3)上网题 (4)文字题 (5)表格题 (6)演示文稿 二、计算机等级考试——标准评分 (1)选…...
Android系统开发 给system/app传包报错
一、现象 adb 命令推送apk到system/app下提示 remote couldnt create file: Read-only file system demo /oem/appsystem app 在Android设备上,/system 分区通常是只读的(Read-only file system),这意味着普通用户或应用程序…...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...
深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...
【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...
企业如何增强终端安全?
在数字化转型加速的今天,企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机,到工厂里的物联网设备、智能传感器,这些终端构成了企业与外部世界连接的 “神经末梢”。然而,随着远程办公的常态化和设备接入的爆炸式…...
