【链表OJ题(六)】链表分割

📝个人主页:@Sherry的成长之路
🏠学习社区:Sherry的成长之路(个人社区)
📖专栏链接:数据结构
🎯长路漫漫浩浩,万事皆有期待
文章目录
- 链表OJ题(六)
- 1. 链表分割
- 思路一 带哨兵位的头结点
- 思路二 不强行加头结点
- 7.总结:
上一篇链表OJ题链接:【链表OJ题(五)】合并两个有序链表
链表OJ题(六)
1. 链表分割
链接:CM11 链表分割
描述:
现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。
思路一 带哨兵位的头结点
题目要求我们将小于 x 的节点和大于等于 x 的节点分隔,小于 x 的节点在前,大于等于 x 的节点在后,且不能改变原来的数据顺序。
不能改变顺序就比较棘手,如果没有这个条件,我们可以用双指针来写。但是题目既然给出了要求,我们就得想办法解决。
我们创建一个新链表存放小于 x 的值,另一个存放大于等于 x 的值。然后遍历原链表,将符合条件的值放入对应的链表中,最后再将存放小于 x 的值的链表和存放大于等于 x 的值的链表链接起来。
那么这过程肯定是尾插,本题使用哨兵位是十分合适的,因为本题有很多的空指针处理的情况,所以我们设定两个哨兵位 lessHead 、 greaterHead。
再给定两个尾lessTail 、 greaterTail,用来尾插。 但是最后记得释放哨兵位。
注意如果以 greaterHead 结束的元素不是链表的最后一个元素(即原链表最后一个元素小于 x ),就可能会造成 链表带环 的情况,因为尾插改变前一个链接关系,没有改变自己的后一个链接关系,所以需要断开环,然后将 greaterTail 的 next 置为空。

代码:
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode* lessTail, *lessHead, *greaterTail, *greaterHead;// 建立哨兵位lessTail = lessHead = (struct ListNode*)malloc(sizeof(struct ListNode));greaterTail = greaterHead = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur = pHead;while (cur){if (cur->val < x){lessTail->next = cur;lessTail = cur;}else{greaterTail->next = cur;greaterTail = cur;}cur = cur->next;}// 链接两个链表lessTail->next = greaterHead->next;greaterTail->next = NULL; // 断开环// 拷贝节点,释放哨兵位struct ListNode* ans = lessHead->next;free(lessHead);free(greaterHead);return ans;}
};

思路二 不强行加头结点
这道题目不用哨兵位也可以做,但是比较考验细节
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode* lessTail, *lessHead, *greaterHead, *greaterTail;lessTail = lessHead = greaterHead = greaterTail = NULL;struct ListNode* cur = pHead;while (cur){if (cur->val < x){if (lessTail == NULL){// 第一次尾插lessHead = lessTail = cur;}else{lessTail->next = cur;lessTail = lessTail->next;}cur = cur->next;}else{if (greaterTail == NULL){// 第一次尾插greaterHead = greaterTail = cur;}else{greaterTail->next = cur;greaterTail = greaterTail->next;}cur = cur->next;}}// lessHead 为空,说明原链表为空或链表的值全大于 x// 且链表尾部的 next 一定为空// 返回 greaterHeadif (lessHead == NULL)return greaterHead;// 如果 lessHead 和 greaterHead 都不为空// 说明正常分割// 将其链接,greaterHead 尾部链空if (lessHead != NULL && greaterHead != NULL){lessTail->next = greaterHead;greaterTail->next = NULL;}// 无论是正常分割,还是链表的值全小于 x// 都是返回 lessHeadreturn lessHead;}
};

7.总结:
今天我们通过两种思路分析并完成链表分割这道链表OJ题目,也更加深层次了解和使用了哨兵位的头结点这个思路,通过这道题我们也能总结出,当面对尾插且需要处理很多空指针的时候,用哨兵位的头节点这个思路很方便。希望我的文章和讲解能对大家的学习提供一些帮助。
当然,本文仍有许多不足之处,欢迎各位小伙伴们随时私信交流、批评指正!我们下期见~

相关文章:
【链表OJ题(六)】链表分割
📝个人主页:Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:数据结构 🎯长路漫漫浩浩,万事皆有期待 文章目录链表OJ题(六)1. 链表…...
C++类中的三大函数(构造,析构,拷贝)
下面一段话与大家共勉:每个人的一生都会遇到很多边界,有些边界可以突破,有些则不能。那些无法突破的边界就是你的极限,而划分边界的标准就是“阈值”。每次突破阈值之后,人生轨迹就会发生剧烈变化,其间需要…...
【2024考研】计算机考研,4轮复习时间安排
文章目录🎨第1轮复习(暑假前&系统课)英语1/2数学1/2专业课408🎨第2轮复习(开学前&真题)英语1/2试卷数学1/2试卷专业课408试卷🎨第3轮复习(报名前&政治)政治试…...
(十二)python网络爬虫(理论+实战)——实战:使用BeautfulSoup解析baidu热搜新闻数据
系列文章: python网络爬虫专栏 目录 序言 本节学习目标 特别申明 4.7 使用BeautfulSoup解析h...
【经验】项目管理:瀑布式、Scrum
1、瀑布式开发 流程关键词关键人员输出立项简述、周期、预算领导立项申请表、立项评审表策划计划项目经理、QA、CM各种计划书(项目、配置、测试等),评审需求功能项目经理功能列表、需求规格书、需求开发计划等,评审设计UML开发设…...
Learning C++ No.17【STL No.7】双端队列
引言: 北京时间:2023/3/17/7:18,刚刚快乐的早锻炼回来(不对 ,应该说回来有一会了),因为此时我已经吃完早饭,洗过澡了;现在回想起上学期,就算是第二天需要晨跑…...
Snackbar
1.简介 位于底部的提示View 支持侧滑消失 同一时间只有一个 不支持跨Activity展示 国内使用率很低 2.基础使用 2.1 基本展示 Snackbar.make(view, "Content", Snackbar.LENGTH_LONG).show()2.2 设置点击事件 注意不设置点击事件回调,点击按钮的文字不…...
HummerRisk 使用教程:主机检测
1. 概述 HummerRisk 是开源的云原生安全平台,以非侵入的方式解决云原生环境的安全和治理问题。核心能力包括混合云的安全治理和容器云安全检测。 本文将介绍HummerRisk中的主机检测部分功能,包括如何管理主机、管理凭证,以及使用主机检测规…...
【Arduino无线气象站项目】
【Arduino无线气象站项目】 1. 概述2. Arduino无线气象站电路图3. 定制设计电路板4. Arduino无线气象站代码5. 总结1. 概述 使用DHT22传感器测量室外温度和湿度,并使用NRF24L01收发器模块将这些数据无线发送到室内机。在室内机,还有另一个用于测量室内温度和湿度的DHT22传感…...
HTTP详解
一,什么是HTTPHTTP(全称为“超文本传输协议”),是一种应用非常广泛的应用层协议,之前在《初识网络原理》的博客(初识网络原理_徐憨憨!的博客-CSDN博客)中,有详细讲解过TCP/IP五层模型,其中应用层描述了数据…...
cpufreq--处理器功耗控制
cpu 功耗控制 参考框架: cpufreq 框架。 cpufreq 框架提供 cpu 功耗管理接口,以及功耗管理方案。 用户可以通过功耗管理接口(以文件形式提供)来选择管理方案,并设置相关参数。 管理方案的实现则由具体的驱动来完成。…...
做技术,最忌讳东张西望
又好长时间没更新,研二了,忙着做实验、写论文、发论文,再加上给我导做一些事情(都习惯了,以前很不爽的事情,现在居然能这么平静的说出来)。 但这不是我今天说的重点,而是另外一件事…...
Oracle 常见报错问题汇总
Oracle 常见报错问题汇总 报错:ORA-01017: invalid username/password; logon denied报错:ORA-01031: insufficient privileges报错:"ORA-01034: ORACLE not available" 和 "ORA-27101: shared memory realm does not exist"报错:“ORA-00119: invalid…...
单片机连接有人云上传数据
首先采用有人物联网的模块 ,连接有人云平台服务器 看云平台相关配置配置连接设备在线后 添加设备添加设备完成后 添加变量模板 变量模板的添加方式如下 :本次采用的是标准的MODbus 协议添加一个温度变量温度变量如下显示云平台 下发数据 采集01 03 00 00…...
系统集成项目管理工程师:第18章项目风险管理学习笔记
第18章项目风险管理 一、目录 18.1 风险概述 18.1.1 风险的定义 18.1.2 风险的分类 18.1.3 风险的性质 18.2 项目风险管理 18.3 规划风险管理 18.3.1 规划风险管理的输入 18.3.2 规划风险管理的工具与技术 18.3.3 规划风险管理的输出 18.4 识别风险...
【笔试强训选择题】Day3.习题(错题)解析
文章目录 前言一、Day3习题(错题)解析二、Day3习题(原题)练习总结前言 今天我们将进入到第三天的练习,希望能一直坚持下去,不断反思总结错误,得到进步; 一、Day3习题(错…...
基于GPT-4的免费代码生成工具
大家好,我是herosunly。985院校硕士毕业,现担任算法研究员一职,热衷于机器学习算法研究与应用。曾获得阿里云天池比赛第一名,CCF比赛第二名,科大讯飞比赛第三名。拥有多项发明专利。对机器学习和深度学习拥有自己独到的见解。曾经辅导过若干个非计算机专业的学生进入到算法…...
Android开发的这一年里,Jetpack的Room源码是怎么狠狠奖励我的?
简述 Android Jetpack的出现统一了Android开发生态,各种三方库逐渐被官方组件所取代。Room也同样如此,逐渐取代竞品成为最主流的数据库ORM框架。这当然不仅仅因为其官方身份,更是因为其良好的开发体验,大大降低了SQLite的使用门槛…...
推荐一款卸载软件的小工具-《UninstallToo》
目录 UninstallToo介绍 UninstallToo下载 UninstallToo使用 总结 UninstallToo介绍 Uninstall Tool 是一款可以用来替代“添加/删除程序”的工具。它允许您显示隐藏的安装程序,按名称过滤已安装程序的列表,强行写在程序,浏览注册表项目&a…...
线程池——JUC随记8
线程池使用方式 1、一池N线程(Executors.newFixedThreadPool(n)) import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors;public class ExecutorDemo {public static void main(String[] args) {ExecutorService execu…...
多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
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; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
抽象类和接口(全)
一、抽象类 1.概念:如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象,这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法,包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中,⼀个类如果被 abs…...
热烈祝贺埃文科技正式加入可信数据空间发展联盟
2025年4月29日,在福州举办的第八届数字中国建设峰会“可信数据空间分论坛”上,可信数据空间发展联盟正式宣告成立。国家数据局党组书记、局长刘烈宏出席并致辞,强调该联盟是推进全国一体化数据市场建设的关键抓手。 郑州埃文科技有限公司&am…...
