【数据结构OJ题】链表分割
原题链接:https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
目录
1. 题目描述
2. 思路分析
3. 代码实现
1. 题目描述

2. 思路分析
整体思路:创建两个链表,分别存放小于x的结点和大于等于x的结点,分别进行尾插。

这道题目使用哨兵位会更简单,原因如下(能避开很多为空的情况):
(1)使用哨兵位就不需要考虑两个链表尾插时为空的情况。
(2)两个链表链接时也不需要考虑是否为空的情况。
(3)哪怕有一个链表为空,也有哨兵位的头结点,正常链接即可。

我们用结构体指针lhead和ltail分别表示值小于x的那一条链表,用结构体指针ghead和gtail表示值大于等于x的那一条链表。
用malloc()函数分别申请两个结点,也就是两个链表的哨兵位,让lhead和ltail一开始指向其中一个,ghead和gtail一开始指向另一个。
再创建一个结构体指针cur用来遍历原链表,我们采用了while循环,当cur不为空时遍历结点。
当结点的值小于x时,我们将这个结点尾插到第一个链表(ltail->next=cur)。再让ltai往后走一步(ltai=ltail->next)。
当结点的值大于等于x时,我们将结点尾插到第二个链表(gtail->next=cur)。再让gtail往后走一 一步(gtail=gtail->next)。
尾插一个结点后,让cur往后走一步(cur=cur->next)。当cur为空时停止循环。
然后将两个链表链接起来。(ltail->next=ghead->next)。
有一点需要非常注意!!!
将gtail->next=NULL
否则可能会出现环。

因为现在lhead指向的是哨兵位,所以我们要将lhead往后走一步(lhead=lhead->next)。
因为怕找不到lhead的下一个位置,所以我们引入一个结构体指针head保存lhead的下一个位置。(struct ListNode *head=lhead->next)。
然后为了防止内存泄漏,我们要用free()释放掉两个哨兵位(即free(lhed)和free(ghead))。
最后返回head即可。

3. 代码实现
/*
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 *lhead,*ltail,*ghead,*gtail;lhead=ltail=(struct ListNode*)malloc(sizeof(struct ListNode));ghead=gtail=(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode *cur=pHead;while(cur){if(cur->val<x){ltail->next=cur;ltail=ltail->next;}else{gtail->next=cur;gtail=gtail->next;}cur=cur->next;}ltail->next=ghead->next;//不空,可能导致出现环gtail->next=NULL;struct ListNode *head=lhead->next;free(lhead);free(ghead);return head;}
};

相关文章:
【数据结构OJ题】链表分割
原题链接:https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId8&&tqId11004&rp2&ru/activity/oj&qru/ta/cracking-the-coding-interview/question-ranking 目录 1. 题目描述 2. 思路分析 3. 代码实现 1. 题目描述 2…...
无感知发布
什么是无感知发布 "无感知发布"是指在软件系统或应用程序进行更新或升级时,尽可能地避免对用户或系统的正常运行产生影响或中断。这种发布方式通常采用一系列技术和策略,以确保新版本的软件可以平滑地替代旧版本,而不会造成用户的…...
C++ 虚继承
C棱形继承 在 C 中,在使用 多继承 时,如果发生了如果类 A 派生出类 B 和类 C,类 D 继承自类 B 和类 C,这时候就发生了菱形继承。 如果发生了菱形继承,这个时候类 A 中的 成员变量 和 成员函数 继承到类 D 中变成了两…...
git commit用法
git commit 是 Git 版本控制系统中的一个命令,用于将更改提交到本地存储库。以下是 git commit 的一些常见用法和选项: 基本用法: git commit -m "提交信息"使用 -m 选项可以直接在命令行中添加提交信息。 提交所有更改: git commit -a -m &q…...
【LeetCode】543.二叉树的直径
题目 给你一棵二叉树的根节点,返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的 长度 由它们之间边数表示。 示例 1: 输入:root [1,2,3,4,5]…...
TypeScript教程(五)条件语句,循环,函数
一、条件语句 条件语句基于不同的条件来执行不同的动作 1.if语句:只有当指定条件为true时,使用该语句来执行代码 2.if...else语句:当条件为true时执行代码,当条件为else时执行其他代码 3.if...else if...else语句:…...
vue使用jsplumb 流程图
安装jsPlumb库:在Vue项目中使用npm或yarn安装jsPlumb库。 npm install jsplumb 创建一个Vue组件:创建一个Vue组件来容纳jsPlumb的功能和呈现。 <template><div style"margin: 20px"><div style"margin: 20px">&l…...
【BASH】回顾与知识点梳理(二十八)
【BASH】回顾与知识点梳理 二十八 二十八. 例行性工作排程(crontab)28.1 什么是例行性工作排程Linux 工作排程的种类: at, cronCentOS Linux 系统上常见的例行性工作 28.2 仅执行一次的工作排程atd 的启动at 的运作方式实际运作单一工作排程at 工作的管理batch&…...
LangChain源码逐行解密之系统(二)
LangChain源码逐行解密之系统 20.2 serapi.py源码逐行剖析 我们可以看一下Google查询的例子,在LangChain中有多种实现的方式。 如图20-5所示,在utilities的serpapi.py代码文件中实现了SerpAPIWrapper。 图20- 5 utilities的serpapi.py的SerpAPIWrapper 在langchain目录的se…...
QT的设计器介绍
设计器介绍 Qt制作 UI 界面,一般可以通过UI制作工具QtDesigner和纯代码编写两种方式来实现。纯代码实现暂时在这里不阐述了在后续布局章节详细说明,QtDesigner已经继承到开发环境中,在工程中直接双击ui文件就可以直接在QtDesigner设计器中打…...
[LitCTF 2023]Ping
因为直接ping会有弹窗。这里在火狐f12,然后f1选禁用javascript,然后ping 然后输入127.0.0.1;cat /flag 得到flag, 查看其他大佬的wp ,这里还可以抓包。但是不知道为什么我这里的burp 用不了...
Spring Cloud面试突击班1
Spring Cloud面试突击班1 1.Spring Cloud 中有哪些组件,整个项目架构中我们的重点又有哪些? Spring Cloud 是一套基于Spring Boot的微服务解决方案。 Spring Cloud生态在国内主流的分为两套,一套是以奈飞开源的Spring Cloud Netfilx 20%&a…...
线上售楼vr全景看房成为企业数字化营销工具
在房地产业中,VR全景拍摄为买家提供了虚拟看房的全新体验。买家可以通过相关设备,远程参观各个楼盘的样板间和实景,感受房屋的空间布局和环境氛围,极大地提高了购房决策的准确性。对于房地产开发商和中介机构来说,VR全…...
“深入探索JVM内部机制:解密Java虚拟机原理“
标题:深入探索JVM内部机制:解密Java虚拟机原理 摘要:本文将深入探索Java虚拟机(JVM)的内部机制,揭示其工作原理和关键组成部分,包括类加载、内存管理、垃圾回收、即时编译和运行时数据区域等。…...
最长 上升子序列
大家好 我是寸铁 希望这篇题解对你有用,麻烦动动手指点个赞或关注,感谢您的关注 不清楚蓝桥杯考什么的点点下方👇 考点秘籍 想背纯享模版的伙伴们点点下方👇 蓝桥杯省一你一定不能错过的模板大全(第一期) 蓝桥杯省一你一定不…...
Nginx的介绍
本资料转载于传智教育-解锁你的IT职业薪未来,仅用于学习和讨论,如有侵权请联系 视频地址:04-Nginx的优点_哔哩哔哩_bilibili 资源文档:链接:https://pan.baidu.com/s/1RlFl92FdxRUqc858JSxPSQ 提取码:12…...
[杂项]奥特曼系列影视列表大全
1966年:《奥特曼》「初代奥特曼」 1967年:《奥特赛文》 1971年:《归来的奥特曼》「杰克奥特曼」 1972年:《艾斯奥特曼》 1973年:《泰罗奥特曼》 1974年:《雷欧奥特曼》 1979年动画版:《乔尼亚斯…...
java代码日记--java 基础语法
java代码日记 在线运行 本地运行环境配置 Java 实例 实战 java8 Java 基础语法 一个Java程序可以认为是一系列对象的集合,而这些对象通过调用彼此的方法来协同工作。 下面简要介绍下类、对象、方法和实例变量的概念。 对象:对象是类的一个实例&…...
Spring中的IOC与DI-细胞内物质与传递
对IOC的认识 Spring Inversion of Control简称Spring IOC,是一种设计原则,通过它可以实现对象之间的解耦。通过Spring DI(Dependency Injection)依赖注入实现对象生命周期管理,为开发者提供对象创建、使用方式。 Spring中的Bean 在Spring框…...
【探索Linux】—— 强大的命令行工具 P.5(yum工具、git 命令行提交代码)
阅读导航 前言一、软件包管理器 yum1.yum的概念yum的基本指令使用例子 二、git 命令行提交代码总结温馨提示 前言 前面我们讲了C语言的基础知识,也了解了一些数据结构,并且讲了有关C的一些知识,也学习了一些Linux的基本操作,也了…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
企业如何增强终端安全?
在数字化转型加速的今天,企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机,到工厂里的物联网设备、智能传感器,这些终端构成了企业与外部世界连接的 “神经末梢”。然而,随着远程办公的常态化和设备接入的爆炸式…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
动态 Web 开发技术入门篇
一、HTTP 协议核心 1.1 HTTP 基础 协议全称 :HyperText Transfer Protocol(超文本传输协议) 默认端口 :HTTP 使用 80 端口,HTTPS 使用 443 端口。 请求方法 : GET :用于获取资源,…...
【从零学习JVM|第三篇】类的生命周期(高频面试题)
前言: 在Java编程中,类的生命周期是指类从被加载到内存中开始,到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期,让读者对此有深刻印象。 目录 …...
【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...
