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

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

在这里插入图片描述

​📝个人主页:@Sherry的成长之路
🏠学习社区:Sherry的成长之路(个人社区)
📖专栏链接:数据结构
🎯长路漫漫浩浩,万事皆有期待

文章目录

  • 链表OJ题(六)
    • 1. 链表分割
      • 思路一 带哨兵位的头结点
      • 思路二 不强行加头结点
  • 7.总结:

上一篇链表OJ题链接:【链表OJ题(五)】合并两个有序链表

链表OJ题(六)

1. 链表分割

链接:CM11 链表分割

描述:
现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。

思路一 带哨兵位的头结点

题目要求我们将小于 x 的节点和大于等于 x 的节点分隔,小于 x 的节点在前,大于等于 x 的节点在后,且不能改变原来的数据顺序

不能改变顺序就比较棘手,如果没有这个条件,我们可以用双指针来写。但是题目既然给出了要求,我们就得想办法解决。

我们创建一个新链表存放小于 x 的值,另一个存放大于等于 x 的值。然后遍历原链表,将符合条件的值放入对应的链表中,最后再将存放小于 x 的值的链表和存放大于等于 x 的值的链表链接起来

那么这过程肯定是尾插,本题使用哨兵位是十分合适的,因为本题有很多的空指针处理的情况,所以我们设定两个哨兵位 lessHeadgreaterHead

再给定两个尾lessTailgreaterTail,用来尾插。 但是最后记得释放哨兵位。

注意如果以 greaterHead 结束的元素不是链表的最后一个元素(即原链表最后一个元素小于 x ),就可能会造成 链表带环 的情况,因为尾插改变前一个链接关系,没有改变自己的后一个链接关系,所以需要断开环,然后将 greaterTailnext 置为空。
在这里插入图片描述

代码:


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题(六)】链表分割

​ ​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;数据结构 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 文章目录链表OJ题(六)1. 链表…...

C++类中的三大函数(构造,析构,拷贝)

下面一段话与大家共勉&#xff1a;每个人的一生都会遇到很多边界&#xff0c;有些边界可以突破&#xff0c;有些则不能。那些无法突破的边界就是你的极限&#xff0c;而划分边界的标准就是“阈值”。每次突破阈值之后&#xff0c;人生轨迹就会发生剧烈变化&#xff0c;其间需要…...

【2024考研】计算机考研,4轮复习时间安排

文章目录&#x1f3a8;第1轮复习&#xff08;暑假前&系统课&#xff09;英语1/2数学1/2专业课408&#x1f3a8;第2轮复习&#xff08;开学前&真题&#xff09;英语1/2试卷数学1/2试卷专业课408试卷&#x1f3a8;第3轮复习&#xff08;报名前&政治&#xff09;政治试…...

(十二)python网络爬虫(理论+实战)——实战:使用BeautfulSoup解析baidu热搜新闻数据

系列文章: python网络爬虫专栏 目录 序言 本节学习目标 特别申明 4.7 使用BeautfulSoup解析h...

【经验】项目管理:瀑布式、Scrum

1、瀑布式开发 流程关键词关键人员输出立项简述、周期、预算领导立项申请表、立项评审表策划计划项目经理、QA、CM各种计划书&#xff08;项目、配置、测试等&#xff09;&#xff0c;评审需求功能项目经理功能列表、需求规格书、需求开发计划等&#xff0c;评审设计UML开发设…...

Learning C++ No.17【STL No.7】双端队列

引言&#xff1a; 北京时间&#xff1a;2023/3/17/7:18&#xff0c;刚刚快乐的早锻炼回来&#xff08;不对 &#xff0c;应该说回来有一会了&#xff09;&#xff0c;因为此时我已经吃完早饭&#xff0c;洗过澡了&#xff1b;现在回想起上学期&#xff0c;就算是第二天需要晨跑…...

Snackbar

1.简介 位于底部的提示View 支持侧滑消失 同一时间只有一个 不支持跨Activity展示 国内使用率很低 2.基础使用 2.1 基本展示 Snackbar.make(view, "Content", Snackbar.LENGTH_LONG).show()2.2 设置点击事件 注意不设置点击事件回调&#xff0c;点击按钮的文字不…...

HummerRisk 使用教程:主机检测

1. 概述 HummerRisk 是开源的云原生安全平台&#xff0c;以非侵入的方式解决云原生环境的安全和治理问题。核心能力包括混合云的安全治理和容器云安全检测。 本文将介绍HummerRisk中的主机检测部分功能&#xff0c;包括如何管理主机、管理凭证&#xff0c;以及使用主机检测规…...

【Arduino无线气象站项目】

【Arduino无线气象站项目】 1. 概述2. Arduino无线气象站电路图3. 定制设计电路板4. Arduino无线气象站代码5. 总结1. 概述 使用DHT22传感器测量室外温度和湿度,并使用NRF24L01收发器模块将这些数据无线发送到室内机。在室内机,还有另一个用于测量室内温度和湿度的DHT22传感…...

HTTP详解

一&#xff0c;什么是HTTPHTTP(全称为“超文本传输协议”)&#xff0c;是一种应用非常广泛的应用层协议&#xff0c;之前在《初识网络原理》的博客(初识网络原理_徐憨憨&#xff01;的博客-CSDN博客)中&#xff0c;有详细讲解过TCP/IP五层模型&#xff0c;其中应用层描述了数据…...

cpufreq--处理器功耗控制

cpu 功耗控制 参考框架&#xff1a; cpufreq 框架。 cpufreq 框架提供 cpu 功耗管理接口&#xff0c;以及功耗管理方案。 用户可以通过功耗管理接口&#xff08;以文件形式提供&#xff09;来选择管理方案&#xff0c;并设置相关参数。 管理方案的实现则由具体的驱动来完成。…...

做技术,最忌讳东张西望

又好长时间没更新&#xff0c;研二了&#xff0c;忙着做实验、写论文、发论文&#xff0c;再加上给我导做一些事情&#xff08;都习惯了&#xff0c;以前很不爽的事情&#xff0c;现在居然能这么平静的说出来&#xff09;。 但这不是我今天说的重点&#xff0c;而是另外一件事…...

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

单片机连接有人云上传数据

首先采用有人物联网的模块 &#xff0c;连接有人云平台服务器 看云平台相关配置配置连接设备在线后 添加设备添加设备完成后 添加变量模板 变量模板的添加方式如下 &#xff1a;本次采用的是标准的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习题&#xff08;错题&#xff09;解析二、Day3习题&#xff08;原题&#xff09;练习总结前言 今天我们将进入到第三天的练习&#xff0c;希望能一直坚持下去&#xff0c;不断反思总结错误&#xff0c;得到进步&#xff1b; 一、Day3习题&#xff08;错…...

基于GPT-4的免费代码生成工具

大家好,我是herosunly。985院校硕士毕业,现担任算法研究员一职,热衷于机器学习算法研究与应用。曾获得阿里云天池比赛第一名,CCF比赛第二名,科大讯飞比赛第三名。拥有多项发明专利。对机器学习和深度学习拥有自己独到的见解。曾经辅导过若干个非计算机专业的学生进入到算法…...

Android开发的这一年里,Jetpack的Room源码是怎么狠狠奖励我的?

简述 Android Jetpack的出现统一了Android开发生态&#xff0c;各种三方库逐渐被官方组件所取代。Room也同样如此&#xff0c;逐渐取代竞品成为最主流的数据库ORM框架。这当然不仅仅因为其官方身份&#xff0c;更是因为其良好的开发体验&#xff0c;大大降低了SQLite的使用门槛…...

推荐一款卸载软件的小工具-《UninstallToo》

目录 UninstallToo介绍 UninstallToo下载 UninstallToo使用 总结 UninstallToo介绍 Uninstall Tool 是一款可以用来替代“添加/删除程序”的工具。它允许您显示隐藏的安装程序&#xff0c;按名称过滤已安装程序的列表&#xff0c;强行写在程序&#xff0c;浏览注册表项目&a…...

线程池——JUC随记8

线程池使用方式 1、一池N线程&#xff08;Executors.newFixedThreadPool(n)&#xff09; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors;public class ExecutorDemo {public static void main(String[] args) {ExecutorService execu…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

(十)学生端搭建

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

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...