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

02.04、分割链表

02.04、[中等] 分割链表

1、题目描述

给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你不需要 保留 每个分区中各节点的初始相对位置。

2、解题思路

本题要求将链表分隔,使得所有小于 x 的节点排在大于或等于 x 的节点之前。链表中的节点顺序不需要保持。我们的目标是创建两个链表,一个存储小于 x 的节点,另一个存储大于等于 x 的节点,最后将两个链表拼接起来。

  1. 创建两个链表:
    • 一个用于存放小于 x 的节点 (less)。
    • 一个用于存放大于等于 x 的节点 (greater)。
  2. 遍历原链表:
    • 对于每个节点,判断其值与 x 的大小:
      • 如果节点值小于 x,将其添加到 less 链表。
      • 如果节点值大于等于 x,将其添加到 greater 链表。
  3. 拼接两个链表:
    • 遍历完原链表后,将 less 链表的最后一个节点指向 greater 链表的头节点。
    • greater 链表的最后一个节点需要指向 null,表示链表的结束。
  4. 返回结果:
    • 返回 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、关键点总结

  1. 虚拟节点:
    • 使用 ListNode() 创建虚拟头节点,避免处理头节点的特殊情况,简化代码逻辑。
  2. 链表拼接:
    • 遍历原链表的过程中,将节点分别加入到 lessgreater 链表。遍历完后,将 less 链表与 greater 链表拼接在一起。
  3. 尾节点处理:
    • 注意在拼接链表后,greater 链表的最后一个节点需要指向 nullptr,防止链表成环。

5、时间复杂度与空间复杂度

  • 时间复杂度: O(n),其中 n 是链表的长度。我们只遍历了链表一次。
  • 空间复杂度: O(1),因为我们只是创建了两个辅助链表指针,额外空间与输入大小无关。

相关文章:

02.04、分割链表

02.04、[中等] 分割链表 1、题目描述 给你一个链表的头节点 head 和一个特定值 x &#xff0c;请你对链表进行分隔&#xff0c;使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 你不需要 保留 每个分区中各节点的初始相对位置。 2、解题思路 本题要求将链表分隔…...

Excel 中根据患者的就诊时间标记病例为“初诊”或“复诊”

1. 假设&#xff1a; 患者表&#xff1a;包含患者的基本信息&#xff0c;如患者 ID 和患者姓名。 病例表&#xff1a;包含病例信息&#xff0c;如患者 ID、就诊时间和就诊状态。 2. 操作步骤&#xff1a; 合并数据&#xff1a; 确保病例表中有一列包含患者 ID&#xff0c;以…...

遇到“mfc100u.dll丢失”的系统错误要怎么处理?科学修复mfc100u.dll

遇到“mfc100u.dll丢失”的系统错误会非常麻烦&#xff0c;因为mfc100u.dll是Microsoft Visual C 2010 Redistributable Package的重要部分&#xff0c;许多应用程序和游戏在运行时都需要调用这个文件。如果这个文件缺失&#xff0c;可能会导致相关软件或游戏启动失败。面对这种…...

[Linux] 逐层深入理解文件系统 (1)—— 进程操作文件

标题&#xff1a;[Linux] 文件系统 &#xff08;1&#xff09;—— 进程操作文件 个人主页水墨不写bug &#xff08;图片来源于网络&#xff09; 目录 一、进程与打开的文件 二、文件的系统调用与库函数的关系 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 初始化和脱离互斥量 概述 本文主要介绍互斥量的概念&#xff0c;实现原理。还介绍RT-Thre…...

6.计算机网络_UDP

UDP的主要特点&#xff1a; 无连接&#xff0c;发送数据之前不需要建立连接。不保证可靠交付。面向报文。应用层给UDP报文后&#xff0c;UDP并不会抽象为一个一个的字节&#xff0c;而是整个报文一起发送。没有拥塞控制。网络拥堵时&#xff0c;发送端并不会降低发送速率。可以…...

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&#xff09;身份损失4&#xff09;Total Loss 实验 摘要 提高图像的…...

Axure重要元件三——中继器表单制作

亲爱的小伙伴&#xff0c;在您浏览之前&#xff0c;烦请关注一下&#xff0c;在此深表感谢&#xff01; 本节课&#xff1a;中继器表单制作 课程内容&#xff1a;利用中继器制作表单 应用场景&#xff1a;台账、表单 案例展示&#xff1a; 步骤一&#xff1a;建立一个背景区…...

DMAIC赋能智能家居:解锁未来生活新篇章!

从清晨自动拉开的窗帘&#xff0c;到夜晚自动调暗的灯光&#xff0c;每一处细节都透露着科技的温度与智慧的光芒。而在这场智能革命的浪潮中&#xff0c;DMAIC&#xff08;定义Define、测量Measure、分析Analyze、改进Improve、控制Control&#xff09;作为六西格玛管理的核心方…...

代码随想录算法训练营第二天| 209.长度最小的子数组 59.螺旋矩阵II 区间和 开发商购买土地

209. 长度最小的子数组 题目&#xff1a; 给定一个包含正整数的数组 nums 和一个正整数 target &#xff0c;找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 &#xff0c;并返回其长度。如果不存在符合条件的子数组&#xff0c;返回 0。 示例&#xff1a; 示例 1…...

mysql隐藏索引

1. 什么是隐藏索引&#xff1f; 在 MySQL 8 中&#xff0c;隐藏索引&#xff08;Invisible Indexes&#xff09;是指一种特殊类型的索引&#xff0c;它并不真正被删除&#xff0c;而是被标记为“不可见”。当索引被标记为不可见时&#xff0c;查询优化器在生成查询计划时将忽略…...

etcd入门到实战

概述&#xff1a;本文将介绍etcd特性、使用场景、基本原理以及Linux环境下的实战操作 入门 什么是etcd&#xff1f; etcd是一个分布式键值存储数据库 关键字解析&#xff1a; 键值存储&#xff1a;存储协议是 key—value 的形式&#xff0c;类似于redis分布式&#xff1a;…...

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 开发领域的经典著作&#xff0c;作者 Joshua Bloch 以丰富的经验和深入的知识&#xff0c;全面…...

Vivado HLS学习

视频链接: 6课&#xff1a;数据类型的转换_哔哩哔哩_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的现代化日志模块&#xff0c;具备窗口事件穿透、拖拽和缩放功能。 Axp Logger文档 特性现代化的UI设计支持点击穿透模式&#xff08;不影响脚本运行&#xff09;监听音量-键切换模式支持窗口操作模式窗口拖拽移动窗口自由缩放清空日志关闭日…...

成都睿明智科技有限公司共创抖音电商新篇章

在当今这个数字化浪潮汹涌的时代&#xff0c;抖音电商以其独特的魅力迅速崛起&#xff0c;成为众多商家竞相追逐的新蓝海。在这片充满机遇与挑战的领域中&#xff0c;成都睿明智科技有限公司凭借其专业的服务、创新的策略和敏锐的市场洞察力&#xff0c;成为了众多商家信赖的合…...

Spark的安装配置及集群搭建

Spark的本地安装配置&#xff1a; 我们用scala语言编写和操作spark&#xff0c;所以先要完成scala的环境配置 1、先完成Scala的环境搭建 下载Scala插件&#xff0c;创建一个Maven项目&#xff0c;导入Scala依赖和插件 scala依赖 <dependency><groupId>org.scal…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...