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

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

Python网页自动化Selenium中文文档

1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API&#xff0c;让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API&#xff0c;你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...

FFmpeg avformat_open_input函数分析

函数内部的总体流程如下&#xff1a; avformat_open_input 精简后的代码如下&#xff1a; int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...