02.04、分割链表
02.04、[中等] 分割链表
1、题目描述
给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你不需要 保留 每个分区中各节点的初始相对位置。
2、解题思路
本题要求将链表分隔,使得所有小于 x 的节点排在大于或等于 x 的节点之前。链表中的节点顺序不需要保持。我们的目标是创建两个链表,一个存储小于 x 的节点,另一个存储大于等于 x 的节点,最后将两个链表拼接起来。
- 创建两个链表:
- 一个用于存放小于
x的节点 (less)。 - 一个用于存放大于等于
x的节点 (greater)。
- 一个用于存放小于
- 遍历原链表:
- 对于每个节点,判断其值与 x 的大小:
- 如果节点值小于
x,将其添加到less链表。 - 如果节点值大于等于
x,将其添加到greater链表。
- 如果节点值小于
- 对于每个节点,判断其值与 x 的大小:
- 拼接两个链表:
- 遍历完原链表后,将
less链表的最后一个节点指向greater链表的头节点。 greater链表的最后一个节点需要指向null,表示链表的结束。
- 遍历完原链表后,将
- 返回结果:
- 返回
less链表的头节点(即跳过辅助节点)。
- 返回
3、代码实现与详细注释
class Solution {
public:ListNode* partition(ListNode* head, int x) {// 创建两个虚拟节点作为新链表的头,一个用于小于x的节点,另一个用于大于等于x的节点ListNode* less = new ListNode(0); // 用于存放小于x的节点ListNode* greater = new ListNode(0); // 用于存放大于等于x的节点// 初始化当前遍历的指针,以及两个链表的末尾指针ListNode *cur = head, *cur1 = less, *cur2 = greater;// 遍历整个链表while (cur) {if (cur->val < x) {// 当前节点值小于x,将该节点加入到less链表cur1->next = cur;cur1 = cur1->next; // 移动less链表末尾指针} else {// 当前节点值大于等于x,将该节点加入到greater链表cur2->next = cur;cur2 = cur2->next; // 移动greater链表末尾指针}// 移动到链表的下一个节点cur = cur->next;}// 将less链表与greater链表连接起来cur1->next = greater->next;// 将greater链表的最后一个节点指向null,避免成环cur2->next = nullptr;// 返回less链表的头节点,跳过第一个虚拟节点return less->next;}
};
4、关键点总结
- 虚拟节点:
- 使用
ListNode()创建虚拟头节点,避免处理头节点的特殊情况,简化代码逻辑。
- 使用
- 链表拼接:
- 遍历原链表的过程中,将节点分别加入到
less或greater链表。遍历完后,将less链表与greater链表拼接在一起。
- 遍历原链表的过程中,将节点分别加入到
- 尾节点处理:
- 注意在拼接链表后,
greater链表的最后一个节点需要指向nullptr,防止链表成环。
- 注意在拼接链表后,
5、时间复杂度与空间复杂度
- 时间复杂度: O(n),其中
n是链表的长度。我们只遍历了链表一次。 - 空间复杂度: O(1),因为我们只是创建了两个辅助链表指针,额外空间与输入大小无关。
相关文章:
02.04、分割链表
02.04、[中等] 分割链表 1、题目描述 给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 你不需要 保留 每个分区中各节点的初始相对位置。 2、解题思路 本题要求将链表分隔…...
Excel 中根据患者的就诊时间标记病例为“初诊”或“复诊”
1. 假设: 患者表:包含患者的基本信息,如患者 ID 和患者姓名。 病例表:包含病例信息,如患者 ID、就诊时间和就诊状态。 2. 操作步骤: 合并数据: 确保病例表中有一列包含患者 ID,以…...
遇到“mfc100u.dll丢失”的系统错误要怎么处理?科学修复mfc100u.dll
遇到“mfc100u.dll丢失”的系统错误会非常麻烦,因为mfc100u.dll是Microsoft Visual C 2010 Redistributable Package的重要部分,许多应用程序和游戏在运行时都需要调用这个文件。如果这个文件缺失,可能会导致相关软件或游戏启动失败。面对这种…...
[Linux] 逐层深入理解文件系统 (1)—— 进程操作文件
标题:[Linux] 文件系统 (1)—— 进程操作文件 个人主页水墨不写bug (图片来源于网络) 目录 一、进程与打开的文件 二、文件的系统调用与库函数的关系 1.系统调用open() 三、内存中的文件描述符表 四、缓冲区…...
RT-Thread 互斥量的概念
目录 概述 1 互斥量定义 1.1 概念介绍 1.2 线程优先级翻转问题 2 互斥量管理 2.1 结构体定义 2.2 函数接口介绍 2.2.1 rt_mutex_create函数 2.2.2 rt_mutex_delete 函数 2.2.3 初始化和脱离互斥量 概述 本文主要介绍互斥量的概念,实现原理。还介绍RT-Thre…...
6.计算机网络_UDP
UDP的主要特点: 无连接,发送数据之前不需要建立连接。不保证可靠交付。面向报文。应用层给UDP报文后,UDP并不会抽象为一个一个的字节,而是整个报文一起发送。没有拥塞控制。网络拥堵时,发送端并不会降低发送速率。可以…...
Windows应急响蓝安服面试
Windows应急响应 蓝队溯源流程 学习Windows应急首先要站在攻击者的角度去学习一些权限维持和权限提升的方法.,文章中的方法其实和内网攻防笔记有类似l红队教你怎么利用 蓝队教你怎么排查 攻防一体,应急响应排查这些项目就可以 端口/服务/进程/后门文件都是为了权限维持,得到s…...
PCL 点云配准-4PCS算法(粗配准)
目录 一、概述 1.1原理 1.2实现步骤 1.3应用场景 二、代码实现 2.1关键函数 2.1.1 加载点云数据 2.1.2 执行4PCS粗配准 2.1.3 可视化源点云、目标点云和配准结果 2.2完整代码 三、实现效果 3.1原始点云 3.2配准后点云 PCL点云算法汇总及实战案例汇总的目录地址链接…...
12、论文阅读:利用生成对抗网络实现无监督深度图像增强
Towards Unsupervised Deep Image Enhancement With Generative Adversarial Network 摘要介绍相关工作传统图像增强基于学习的图像增强 论文中提出的方法动机和目标网络架构损失函数1) 质量损失2) 保真损失3)身份损失4)Total Loss 实验 摘要 提高图像的…...
Axure重要元件三——中继器表单制作
亲爱的小伙伴,在您浏览之前,烦请关注一下,在此深表感谢! 本节课:中继器表单制作 课程内容:利用中继器制作表单 应用场景:台账、表单 案例展示: 步骤一:建立一个背景区…...
DMAIC赋能智能家居:解锁未来生活新篇章!
从清晨自动拉开的窗帘,到夜晚自动调暗的灯光,每一处细节都透露着科技的温度与智慧的光芒。而在这场智能革命的浪潮中,DMAIC(定义Define、测量Measure、分析Analyze、改进Improve、控制Control)作为六西格玛管理的核心方…...
代码随想录算法训练营第二天| 209.长度最小的子数组 59.螺旋矩阵II 区间和 开发商购买土地
209. 长度最小的子数组 题目: 给定一个包含正整数的数组 nums 和一个正整数 target ,找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 ,并返回其长度。如果不存在符合条件的子数组,返回 0。 示例: 示例 1…...
mysql隐藏索引
1. 什么是隐藏索引? 在 MySQL 8 中,隐藏索引(Invisible Indexes)是指一种特殊类型的索引,它并不真正被删除,而是被标记为“不可见”。当索引被标记为不可见时,查询优化器在生成查询计划时将忽略…...
etcd入门到实战
概述:本文将介绍etcd特性、使用场景、基本原理以及Linux环境下的实战操作 入门 什么是etcd? etcd是一个分布式键值存储数据库 关键字解析: 键值存储:存储协议是 key—value 的形式,类似于redis分布式:…...
Build an Android project and get a `.apk` file on a Debian 11 command line
You can build an Android project and get a .apk file on a Debian 11 command line without using Android Studio. The process involves using the Android SDK command-line tools (sdkmanager, adb, and gradle). Here’s a step-by-step guide to building the ???…...
解读 Java 经典巨著《Effective Java》90条编程法则,第4条:通过私有构造器强化不可实例化的能力
文章目录 【前言】欢迎订阅【解读《Effective Java》】系列专栏java.lang.Math 类的设计经验总结 【前言】欢迎订阅【解读《Effective Java》】系列专栏 《Effective Java》是 Java 开发领域的经典著作,作者 Joshua Bloch 以丰富的经验和深入的知识,全面…...
Vivado HLS学习
视频链接: 6课:数据类型的转换_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1bt41187RW?spm_id_from333.788.videopod.episodes&vd_sourcea75d5585c5297210add71187236ec90b&p6 目录 1.数据类型的转换 2.自动类型转换 2.1隐式数据转换 2.2…...
一款AutoXJS现代化美观的日志模块AxpLogger
简介 Axp Logger是一款基于autox.js的现代化日志模块,具备窗口事件穿透、拖拽和缩放功能。 Axp Logger文档 特性现代化的UI设计支持点击穿透模式(不影响脚本运行)监听音量-键切换模式支持窗口操作模式窗口拖拽移动窗口自由缩放清空日志关闭日…...
成都睿明智科技有限公司共创抖音电商新篇章
在当今这个数字化浪潮汹涌的时代,抖音电商以其独特的魅力迅速崛起,成为众多商家竞相追逐的新蓝海。在这片充满机遇与挑战的领域中,成都睿明智科技有限公司凭借其专业的服务、创新的策略和敏锐的市场洞察力,成为了众多商家信赖的合…...
Spark的安装配置及集群搭建
Spark的本地安装配置: 我们用scala语言编写和操作spark,所以先要完成scala的环境配置 1、先完成Scala的环境搭建 下载Scala插件,创建一个Maven项目,导入Scala依赖和插件 scala依赖 <dependency><groupId>org.scal…...
HarmonyOS6 ArkTS NavDestination
文章目录核心特性基础使用规范1. 组件层级关系2. 核心属性配置(1)标题配置:title()(2)返回按钮控制:hideBackButton()完整示例完整代码核心功能实现解析1. 主/子页面切换2. 滚动与标题栏联动(核…...
docker容器最大压缩
压缩前先查找出无用的占用空间内容:find / -type f -size 10M -exec ls -lh {} \;上面大于10M的文件都搜出来了压缩容器为镜像:最大压缩(代价时间长):docker export 容器ID | gzip -9 > 名字.tar.gz一般压缩&#x…...
RISC-V 基金会 Data Center SIG 第八次会议圆满结束,围绕AIOE和TG推进展开
一直以来,龙蜥社区在 RISC-V 生态建设中持续投入,并积极贡献上游社区。RISC-V International Data Center SIG 第八次会议内容见下: Atomic I/O Enqueue(AIOE )扩展提案 v4 提案评审 RISC-V International Data Cent…...
Redis持久化:从AOF到RDB,如何实现数据不丢失?共
Qt是一个跨平台C图形界面开发库,利用Qt可以快速开发跨平台窗体应用程序,在Qt中我们可以通过拖拽的方式将不同组件放到指定的位置,实现图形化开发极大的方便了开发效率,本笔记将重点介绍QSpinBox数值微调组件的常用方法及灵活应用。…...
企业年会春联批量生成方案:Pixel Couplet Gen 结合Java八股文风格创作
企业年会春联批量生成方案:Pixel Couplet Gen 结合Java八股文风格创作 1. 场景痛点:企业年会的文化需求与技术创意 每到年末,行政部门的同事总会面临一个看似简单却令人头疼的任务——为企业年会准备定制化春联。传统方式要么花钱请人创作&…...
如何突破抖音视频下载限制:douyin-downloader的全方位解决方案
如何突破抖音视频下载限制:douyin-downloader的全方位解决方案 【免费下载链接】douyin-downloader A practical Douyin downloader for both single-item and profile batch downloads, with progress display, retries, SQLite deduplication, and browser fallba…...
论文阅读:arxiv 2026 From Assistant to Double Agent: Formalizing and Benchmarking Attacks on OpenClaw for
总目录 大模型安全研究论文整理 2026年版:https://blog.csdn.net/WhiffeYF/article/details/159047894 From Assistant to Double Agent: Formalizing and Benchmarking Attacks on OpenClaw for Personalized Local AI Agent https://arxiv.org/abs/2602.08412 该…...
读了50篇文献还是理不清脉络?百考通AI 5分钟生成有主线、有批判的文献综述
在高校学术写作中,文献综述是连接已有研究与创新探索的关键桥梁。它不仅体现作者对领域现状的掌握程度,更直接影响后续研究的深度与可行性。然而,对许多学生而言,撰写一篇专业、规范、有逻辑的综述常常令人望而却步——资料庞杂、…...
Arduino Portenta H7低功耗库深度解析:Sleep/Deep Sleep/Standby三模式实战
1. 项目概述Arduino Portenta H7 Low Power Library 是专为 Arduino Portenta H7 开发板设计的底层功耗管理库,其核心目标是为嵌入式开发者提供对 STM32H747XI 双核微控制器(Cortex-M7 Cortex-M4)全层级低功耗模式的细粒度控制能力。该库并非…...
避坑!这些毕设太好抄了,3000+毕设案例推荐第1042期
421、基于Java的战时医疗保障智慧管理系统的设计与实现(论文+代码+PPT)战时医疗保障智慧管理系统主要功能包括:会员管理、科室管理、医生管理、护士管理、病人管理、病房管理、住院记录、医疗设备、设备维护记录、药品管理、药品库存、采购订…...
