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

7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...

相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...

OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官
。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量:setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...