排序链表--字节跳动
少年的书桌上没有虚度的光阴
题目描述
请你对链表进行排序
思路分析
-
核心思想:归并排序
有三个部分
链表排序实现
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),这意味着普通用户或应用程序…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果
一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库,分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷,但是文件存放起来数据比较冗余,用二进制能够更好管理咱们M…...
免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...
08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险
C#入门系列【类的基本概念】:开启编程世界的奇妙冒险 嘿,各位编程小白探险家!欢迎来到 C# 的奇幻大陆!今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类!别害怕,跟着我,保准让你轻松搞…...
鸿蒙(HarmonyOS5)实现跳一跳小游戏
下面我将介绍如何使用鸿蒙的ArkUI框架,实现一个简单的跳一跳小游戏。 1. 项目结构 src/main/ets/ ├── MainAbility │ ├── pages │ │ ├── Index.ets // 主页面 │ │ └── GamePage.ets // 游戏页面 │ └── model │ …...
