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

排序链表--字节跳动

少年的书桌上没有虚度的光阴

题目描述

请你对链表进行排序

思路分析

  • 核心思想:归并排序

有三个部分

链表排序实现

1. merge 函数

21.见 合并两个有序链表,

  • 首先创建一个虚拟头节点 newhead,并使用指针 tail 来构建合并后的链表。

  • 通过循环比较 list1list2 节点的值,将较小值的节点连接到 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)

相关文章:

排序链表--字节跳动

少年的书桌上没有虚度的光阴 题目描述 请你对链表进行排序 思路分析 核心思想&#xff1a;归并排序 有三个部分 链表排序实现 1. merge 函数 21.见 合并两个有序链表&#xff0c; 首先创建一个虚拟头节点 newhead&#xff0c;并使用指针 tail 来构建合并后的链表。 通过…...

Python爬虫-批量爬取股票数据猫各股票代码

前言 本文是该专栏的第47篇,后面会持续分享python爬虫干货知识,记得关注。 本文笔者以股票数据猫为例子,基于Python爬虫,批量获取各股票代码数据。 具体实现思路和详细逻辑,笔者将在正文结合完整代码进行详细介绍。废话不多说,下面跟着笔者直接往下看正文详细内容。(附…...

打开Firefox自动打开hao360.hjttif.com标签解决方案

现象 打开Firefox自动打开hao360.hjttif.com标签&#xff0c;同时用户自己设置的主页也会在一个新标签打开。点击hjttif这个标签&#xff0c;就会跳转到hao.360.com 打开Edge不会出现上述现象。搜遍全网都找不到解决方法。博客园上有一篇文章2025-02-14.防流氓软件篡改主页提到…...

【爬虫基础】第一部分 网络通讯-编程 P3/3

上节内容回顾&#xff1a;【爬虫基础】第一部分 网络通讯 P1/3-CSDN博客 【爬虫基础】第一部分 网络通讯-Socket套接字 P2/3-CSDN博客 相关文档&#xff0c;希望互相学习&#xff0c;共同进步 风123456789&#xff5e;-CSDN博客 前言 1.知识点碎片化&#xff1a;每个网站实现…...

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.…...

《论软件的可靠性评价》审题技巧 - 系统架构设计师

论软件的可靠性评价写作框架 一、考点概述 软件可靠性评价作为软件可靠性活动的关键环节&#xff0c;是确保软件质量、提升用户体验的重要手段。本题主要考察以下几个方面的内容&#xff1a; 首先&#xff0c;本题要求考生理解并掌握软件可靠性评价的基本概念及其在软件开发…...

【项目设计】自主HTTP服务器

目录 项目介绍 网络协议栈介绍 协议分层 数据的封装与分用 HTTP相关知识介绍 HTTP的特点 URL格式 URI、URL、URN HTTP的协议格式 HTTP响应协议格式 HTTP的请求方法 HTTP的状态码 HTTP常见的Header CGI机制介绍 CGI机制的概念 CGI机制的实现步骤 CGI机制的意义 …...

Linux操作系统:基于Linux的个人Web服务器搭建与自动化运维实践

基于Linux的个人Web服务器搭建与自动化运维实践 摘要 在互联网的海洋中&#xff0c;每个人都想拥有一艘属于自己的小船——一个个人Web服务器。Linux作为开源界的“老大哥”&#xff0c;无疑是搭建Web服务器的最佳选择。本文通过幽默风趣的方式&#xff0c;详细介绍了在Linux…...

[创业之路-321]:创新开拓思维和经营管理思维的比较

目录 一、概述 1.1、定义与内涵 1、创新开拓思维&#xff1a; 2、经营管理思维&#xff1a; 1.2、特点与优势 1、创新开拓思维的特点与优势&#xff1a; 2、经营管理思维的特点与优势&#xff1a; 3、应用场景与限制 4、总结 二、创新开拓思维与经营管理思维&#xf…...

vivado修改下载器下载速率

Error Launching Program X Error while launching program: fpga configuration failed. DONE PIN is not HIGH 原因是下载器速度太快了。先从任务管理器中关闭hw_server.exe试一下,要是不行就按下面三种方法解决。 第一种方法可以不用修改下载速度,直接先从vivado中将bit流…...

运维基线方案说明

1. 总体思路 建立运维基线的核心目标是保障系统稳定性、提升安全性、及时响应异常事件并不断优化系统性能。初创公司资源有限&#xff0c;方案应尽可能简单、易用&#xff0c;同时具备一定的自动化和标准化能力。建议从以下几个层面入手&#xff1a; 标准化文档&#xff1a;制…...

pycharm中配置PyQt6详细教程

PyQt6 是 Qt 框架的 Python 绑定库,基于 Qt 6 开发,专为创建跨平台图形用户界面(GUI)应用程序设计。 本章教程,主要记录在pycharm中配置使用PyQt6的流程。 一、安装基础环境 在此之前,你需要提前安装好Python解释器,推荐使用anaconda创建虚拟环境。 conda create -n pyt…...

大湾区经济网报道:2025春运收官 全国跨区流动90亿,大湾区12亿人次

&#xff08;原标题&#xff1a;2025年春运收官&#xff1a;全国跨区流动超90亿人次 大湾区贡献12亿人次&#xff09; 大湾区经济网2月23日电&#xff08;记者 余芳&#xff09;2025年春运昨日&#xff08;2月22日&#xff09;正式结束&#xff0c;全国跨区域人员流动量达90.2…...

Docker用户的困境:免费项目的减少与成本的增加

摘要 在生产环境中&#xff0c;Docker用户正面临新的挑战&#xff1a;免费项目逐渐减少&#xff0c;收费服务成为主流趋势。表面上免费的选项&#xff0c;由于缺乏必要的支持和及时更新&#xff0c;反而可能导致更高的隐性成本。对于依赖Docker进行开发和部署的企业而言&#x…...

1.4 嵌入式系统的软件

嵌入式系统的开发流程中&#xff0c;硬件和固件设计完成后&#xff0c;嵌入式软件承担起实现功能、用户交互、系统集成和性能优化等任务&#xff1b;嵌入式系统软件分为设备驱动、操作系统和应用程序三个层面。 因此嵌入式系统软件开发工程师通常分为三类&#xff1a;嵌入式系统…...

PHP2(WEB)

##解题思路 打开页面什么线索都没有&#xff0c;目录扫描只是扫出来一个index.php&#xff0c;而源代码没有东西&#xff0c;且/robots.txt是不允许访问的 于是一番查询后发现&#xff0c;有个index.phps的文件路径&#xff0c;里头写着一段php的逻辑&#xff0c;对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…...

一、计算机等级考试——题库

&#xff08;1&#xff09;选择题 &#xff08;2&#xff09;基本操作题 &#xff08;3&#xff09;上网题 &#xff08;4&#xff09;文字题 &#xff08;5&#xff09;表格题 &#xff08;6&#xff09;演示文稿 二、计算机等级考试——标准评分 &#xff08;1&#xff09;选…...

Android系统开发 给system/app传包报错

一、现象 adb 命令推送apk到system/app下提示 remote couldnt create file: Read-only file system demo /oem/appsystem app 在Android设备上&#xff0c;/system 分区通常是只读的&#xff08;Read-only file system&#xff09;&#xff0c;这意味着普通用户或应用程序…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

SpringAI实战:ChatModel智能对话全解

一、引言&#xff1a;Spring AI 与 Chat Model 的核心价值 &#x1f680; 在 Java 生态中集成大模型能力&#xff0c;Spring AI 提供了高效的解决方案 &#x1f916;。其中 Chat Model 作为核心交互组件&#xff0c;通过标准化接口简化了与大语言模型&#xff08;LLM&#xff0…...

上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式

简介 在我的 QT/C 开发工作中&#xff0c;合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式&#xff1a;工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...

Python实现简单音频数据压缩与解压算法

Python实现简单音频数据压缩与解压算法 引言 在音频数据处理中&#xff0c;压缩算法是降低存储成本和传输效率的关键技术。Python作为一门灵活且功能强大的编程语言&#xff0c;提供了丰富的库和工具来实现音频数据的压缩与解压。本文将通过一个简单的音频数据压缩与解压算法…...