当前位置: 首页 > 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…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...