[C/C++]数据结构 链表OJ题: 链表分割

news/2024/2/28 10:42:47

题目描述:

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

解题思路:

        创建两个新链表,head1,head2, 遍历原链表,把小于x的结点尾插到head1链表中,把大于等于x的结点尾插到head2链表,最后链接head1和head2,这个题代码实现起来很简单,但是要注意的是几种特殊情况,比如分类后head1为空或head2为空等情况,还需要用if语句单独判断,包括代码中使用结点的next,都需要提前判断一下该结点是否为空,所以我们可以给这两个新链表加上哨兵位,这样就不需要head1,head2就永远不会为空,这样就可以省去很多单独判断语句

简单介绍一下哨兵位:

       单链表分为带头结点和不带头结点两种情况。带头结点的第一个节点叫哨兵位,属于附加的链表节点,不保存有效数值,只储存第一个有效节点的地址,负责找到第一个节点。

代码实现:


class Partition {
public:ListNode* partition(ListNode* pHead, int x) {//带哨兵位ListNode* head1,*tail1,*head2,*tail2;head1=tail1=(ListNode*)malloc(sizeof(ListNode));head2=tail2=(ListNode*)malloc(sizeof(ListNode));ListNode* cur=pHead;//小于x的结点尾插到head1,大于x的结点尾插到head2while(cur){if(cur->val<x){tail1->next=cur;tail1=tail1->next;}else {tail2->next=cur;tail2=tail2->next;}cur=cur->next;}//链接两个链表tail1->next=head2->next;tail2->next=NULL;pHead=head1->next;free(head1);free(head2);return pHead;}
};


http://www.ppmy.cn/news/1202312.html

相关文章

http和https分别是什么?

HTTP&#xff08;Hypertext Transfer Protocol&#xff09;和HTTPS&#xff08;HTTP Secure&#xff09;是互联网上应用最为广泛的两类协议&#xff0c;都是用于在网络中进行数据交换。 1.HTTP&#xff1a; HTTP是一种无状态的协议&#xff0c;即服务器并不保持与客户端的连接…

【SQL篇】一、Flink动态表与流的关系以及DDL语法

文章目录 1、启动SQL客户端2、SQL客户端常用配置3、动态表和持续查询4、将流转为动态表5、用SQL持续查询6、动态表转为流7、时间属性8、DDL-数据库相关9、DDL-表相关 1、启动SQL客户端 启动Flink&#xff08;基于yarn-session模式为例&#xff09;&#xff1a; /opt/module/f…

92.更新一些收藏的经验贴总结学习

一、JS相关 1.进制转换 &#xff08;1&#xff09;十进制转二进制 十进制数除2取余法&#xff1a;十进制数除2&#xff0c;余数为权位上的数&#xff0c;得到的商继续除2&#xff0c;直到商为0。最后余数从下往上取值。 &#xff08;2&#xff09;二进制转十进制 把二进制…

测试面试题集锦(四)| Linux 与 Python 编程篇(附答案)

本系列文章总结归纳了一些软件测试工程师常见的面试题&#xff0c;主要来源于个人面试遇到的、网络搜集&#xff08;完善&#xff09;、工作日常讨论等&#xff0c;分为以下十个部分&#xff0c;供大家参考。如有错误的地方&#xff0c;欢迎指正。有更多的面试题或面试中遇到的…

ARMday1

1、计算机的组成 输入设备-输出设备-运算器-控制器-存储器 输入设备&#xff1a;键盘、鼠标、手柄、扫描仪 输出设备&#xff1a;显示屏、打印机、音响 存储器&#xff1a;存放数据以及指令、是实现“程序存储控制”的基础、外存、内存、cache、寄存器 控制器&#xff08;…

微服务使用指南

微服务使用指南 1.初识微服务 微服务可以认为是一种分布式架构的解决方案&#xff0c;提供服务的独立性和完整性&#xff0c;做到服务的高内聚、低耦合。 目前服务架构主要包含&#xff1a;单体架构和分布式架构。 1.1 单体架构 单体架构&#xff1a;把所有业务功能模块都…

【公益案例展】中国水利水电科学研究院——云从科技青海湖湟鱼监测保护项目...

‍ 云从科技公益案例 本项目案例由云从科技投递并参与数据猿与上海大数据联盟联合推出的 #榜样的力量# 《2023中国数据智能产业最具社会责任感企业》榜单/奖项”评选。 大数据产业创新服务媒体 ——聚焦数据 改变商业 1994年青海湖裸鲤被列为国家二级保护动物&#xff0c;2003…

Java 设计模式——状态模式

目录 1.概述2.结构3.案例实现3.1.抽象状态类3.2.具体状态类3.3.上下文类3.4.测试 4.优缺点5.使用场景 1.概述 【例】通过按钮来控制一个电梯的状态&#xff0c;电梯有开门状态&#xff0c;关门状态&#xff0c;停止状态&#xff0c;运行状态。每一种状态改变&#xff0c;都有可…

麒麟信安协办 | 2023工业控制系统产业大会隆重举办

11月3日&#xff0c;由中国高科技产业化研究会、湖南省科学技术协会、国防科技大学、湖南大学、中南大学共同主办&#xff0c;工业控制系统产业联盟、长沙经济技术开发区管委会等单位共同承办&#xff0c;麒麟信安等单位协办的“2023 工业控制系统产业大会”在长沙召开。此次会…

如何选择SVM中最佳的【核函数】

参数“kernel"在sklearn中可选以下几种 选项&#xff1a; 接下来我们 就通过一个例子&#xff0c;来探索一下不同数据集上核函数的表现。我们现在有一系列线性或非线性可分的数据&#xff0c;我们希望通过绘制SVC在不同核函数下的决策边界并计算SVC在不同核函数下分类准确…

使用Python从零实现多分类SVM

本文将首先简要概述支持向量机及其训练和推理方程&#xff0c;然后将其转换为代码以开发支持向量机模型。之后然后将其扩展成多分类的场景&#xff0c;并通过使用Sci-kit Learn测试我们的模型来结束。 SVM概述 支持向量机的目标是拟合获得最大边缘的超平面(两个类中最近点的距…

软考高级系统架构设计师系列案例考点专题六:面向服务架构设计

软考高级系统架构设计师系列案例考点专题六:面向服务架构设计 一、面向服务架构设计内容大纲二、SOA概述和发展三、SOA和微服务的区别四、SOA的参考架构五、SOA主要协议和规范六、SOA设计标准和原则七、SOA设计模式八、SOA构建和实施一、面向服务架构设计内容大纲 SOA概述和发…

Window 11中安装Rust编译环境和集成开发环境

https://blog.csdn.net/weixin_43882409/article/details/87616268是我参考的一篇文章。 下载 先到https://www.rust-lang.org/learn/get-started&#xff0c;下载64-Bit&#xff08;64位&#xff09;的rustup-init.exe文件。 使用其他方式进行安装的网址https://forge.rust…

五表联筛:从五个表格中筛选出出现过两次及两次以上的人名

五表联筛&#xff1a;从五个表格中筛选出出现过两次及两次以上的人名 需求分析&#xff1a; 1.把五个表格合并起来&#xff0c;合并之前必须确保五个表格的项是一样 2.合并之后查找哪些人出现过两次 3.最后输出结果代码&#xff1a; def delete_from(self):# 读取五份表格文件…

leetcode2054

leetcode 2054 #include <iostream> #include <vector> #include <tuple> #include <algorithm>using namespace std;struct Event {// 时间戳int ts;// op 0 表示左边界&#xff0c;op 1 表示右边界int op;int val;Event(int _ts, int _op, int _v…

钉钉企业微应用开发C#-HTTP回调接口

官方的STREAM回调推送的方式&#xff0c;试了几次都认证不过&#xff0c;就放弃了还是用HTTP的模式吧。 /// <summary>/// 应用回调/// </summary>/// <param name"model"></param>/// <returns></returns>public static Dictio…

[第二章—Spring MVC的高级技术] 2.1Spring MVC配置的替代方案

7.1.1 自定义DispatcherServlet配置 例如&#xff0c;在本章稍后的内容中&#xff08;7.2节&#xff09;&#xff0c;我们将会看到如何在Spring MVC中处理multipart请求和文件上传。 如果计划使用Servlet 3.0对multipart配置的支持&#xff0c;那么需要使用DispatcherServlet的…

Vue中模板语法与el 和 data 的两种写法

模板语法 标签语法 //在.html文件中 <body><h3>{{name}}</h3> </body> <script>new Vue({el:#root,data:{name:jack,url:网页地址}}) </script> 指令语法 标签语法和指令语法的简单区分&#xff0c;就是指令语法用v-on,v-bind,v-model指…

前端 JS 经典:ES6 和 CommonJs 用法

1. 概念 都是 JavaScript 模块化规范&#xff0c;ES6 适用于浏览器端和 Node.js&#xff0c;CommonJs 适用于 Node.js。 2. 导出 // ES6 export function demo(n1, n2) {return n1 n2; }// CommonJS module.exports {demo: function (n1, n2) {return n1 n2;}, }; 3. 引入 …

响应式招标投标网站模板源码带后台

模板信息&#xff1a; 模板编号&#xff1a;29165 模板编码&#xff1a;UTF8 模板分类&#xff1a;博客、文章、资讯、其他 适合行业&#xff1a;招标类企业 模板介绍&#xff1a; 本模板自带eyoucms内核&#xff0c;无需再下载eyou系统&#xff0c;原创设计、手工书写DIVCSS&a…
最新文章