单链表OJ题(3):合并两个有序链表、链表分割、链表的回文结构
目录
一、合并两个有序链表
二、链表分割
三、链表的回文结构
u解题的总体思路:
合并两个有序链表:首先创建新链表的头节点(哨兵位:本质上是占位子),为了减少一些判断情况,简化操作。然后我们再创建俩个指针分别指针两个单链表的头,然后遍历比较,将两个指针指向节点的最小值接在新链表的后面。
链表分割:创建两个新链表lessHead和greatHead,一个存储原链表中小于x的节点,一个存储其他的节点,我们按顺序遍历原链表:当循环结束后,我们将存储小于x的节点的新链表lessHead接在另一个新链表greatHead的前面。
链表的回文结构:我们利用前面OJ题中的方法,找中间节点(快慢指针),反转链表(三指针法)解这道题,我们找到中间节点后,将中间节点后面的节点的指向反转,然后我们遍历这个反转后的链表与原链表比较,看是否满足条件。
一、合并两个有序链表

步骤1:
我们新建一个链表,初始化NewHead,NewTail三个指针都指向头节点NewList,然后,我们创建指针l1,l2分别指向list1和list2.

步骤2:当l1和l2指向的节点都不为NULL,循环遍历节点,将最小值的节点接在新链表的后面,然后NewTail指向新链表的最后的节点位置上。

步骤3:
我们将l1和l2指向链表节点不为NULL的接在NewTail的next域上,就完成了合并操作。

/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {ListNode *l1 = list1,*l2 = list2; ListNode *NewList = (ListNode*)malloc(sizeof(ListNode)); //创建头节点ListNode * NewHead, *NewTail; NewHead = NewTail = NewList; //初始化俩个指针都指向新链表//l1 和 l2 当前节点都不为NULL,遍历while(l1 && l2){if(l1->val < l2->val){NewTail->next = l1;l1 = l1->next; //l1往后走}else{NewTail->next = l2;l2 = l2->next; //l2往后走}NewTail = NewTail->next; //更新NewTail 指向当前新插入的节点}//两者有一个为NULL(不可能同时为NULL)if(l1!=NULL){NewTail->next=l1;}else{NewTail->next=l2;}return NewList->next;
}
二、链表分割
步骤1:
我们首先创建两个新的链表,lessHead存储节点值< x的节点,greatHead存储节点值>= x的节点。

步骤2:
我们循环原链表,将每个节点按照判断接在各自的新链表中。

步骤3:
我们将lessHead的lessTail的next域接在greatHead的next前面,这样我们就实现了两个新链表的拼接.(注意:最后要将greatTail的next域置为NULL,防止死循环)
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
#include <functional>
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {ListNode *pcur = pHead;//创建俩个头节点,分别存储小节点,和大节点ListNode *lessHead = (ListNode*)malloc(sizeof(ListNode));ListNode *lessTail = lessHead;ListNode *greatHead = (ListNode*)malloc(sizeof(ListNode));ListNode *greatTail = greatHead;//循环遍历原链表中的每个节点while(pcur){if(pcur->val < x){lessTail->next = pcur;lessTail = lessTail->next; //尾指针后移当新插入的节点 }else{greatTail->next = pcur;greatTail = greatTail->next; //尾节点后移到新插入的节点}pcur = pcur->next;}//拼接两个新链表,将lessHead接入到greatHead后面lessTail->next = greatHead->next;greatTail->next = NULL; //将最后的节点next域置为NULLreturn lessHead->next;}
};
三、链表的回文结构

步骤1:
我们首先写出找中间节点的函数middleNode,和反转链表的函数reverseList,找到中间节点,然后,将中间节点后面的链表反转。(这两个函数在上个文章中详细讲解过,这里不再重点讲述)
步骤2:
反转以mid为头节点的链表。

从这里可以看出我们的链表变成了俩个部分,然后我们遍历这两个链表,比较各自节点的值是否相等,相等说明我们原链表就是回文链表。

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public://反转链表ListNode* reverseList(ListNode* head){ListNode*n1,*n2,*n3;n1 = NULL;n2 = head;if(n2==NULL){return NULL;}n3 = n2->next;while(n2){n2->next = n1;n1 = n2;n2 = n3;if(n3)n3 = n3->next;}return n1;}//找中间节点ListNode* middleNode(ListNode* head){if(head==NULL){return NULL;}ListNode *slow,*fast;slow = fast = head;while(fast && fast->next){slow = slow->next; //slow走一步fast = fast->next->next; //fast走两步}return slow;}bool chkPalindrome(ListNode* A) {ListNode*phead = A;ListNode*mid = middleNode(A); //找中间节点ListNode*pcur = reverseList(mid); //反转以中间节点为头的后面的节点while(pcur){if(pcur->val != phead->val){return false;}pcur = pcur->next;phead = phead->next;}//循环正常结束,返回truereturn true;}
};
相关文章:
单链表OJ题(3):合并两个有序链表、链表分割、链表的回文结构
目录 一、合并两个有序链表 二、链表分割 三、链表的回文结构 u解题的总体思路: 合并两个有序链表:首先创建新链表的头节点(哨兵位:本质上是占位子),为了减少一些判断情况,简化操作。然后我们…...
研究了100个小绿书十万加之后,我们发现2024小绿书独家秘籍就是:在于“先抄后超,持续出摊,量大管饱”!
小绿书作为今年最大的红利,很多人已经吃到了螃蟹。看——: 今天我们总结了100个10万爆款,我们发现要在这个平台上脱颖而出,找到属于自己的方法尤为重要。在这里分享一个主题——小绿书的秘诀就是“先抄后超,持续出摊”…...
Java 中 HashMap集合使用
目录 一. HashMap概述 二. HashMap特点 三. HashMap构造方法 四. HashMap的常用方法 五. 使用注意事项 六. 代码示例 一. HashMap概述 HashMap 是 Java 中的一个非常重要的类,它实现了 Map 接口,用于存储键值对(key-value pairs&#…...
#渗透测试#SRC漏洞挖掘# 信息收集-Shodan进阶之Mongodb未授权访问
免责声明 本教程仅为合法的教学目的而准备,严禁用于任何形式的违法犯罪活动及其他商业行为,在使用本教程前,您应确保该行为符合当地的法律法规,继续阅读即表示您需自行承担所有操作的后果,如有异议,请立即停…...
平台化运营公司如何在创业市场招商
在当今商业环境中,平台化运营的公司正成为推动经济发展的重要力量。对于这类公司而言,在创业市场招商意义重大。 平台化运营公司具有独特特点:通过搭建开放共享平台连接供需双方,实现资源优化配置与价值创造。比如电子商务平台、社…...
飞书API-获取tenant_access_token
1.在飞书工作台创建应用,跳到开发者后台,选创建企业自建应用 2.设置并发布应用 必须要发布应用才可以开始使用了!!! 3.调用获取token的API 参考链接: 开发文档 - 飞书开放平台https://open.feishu.cn/do…...
(新)docker desktop镜像迁移
背景 docker desktop默认安装在系统c盘,久而久之随着镜像拉取的越多,系统盘占用则越来越大。现有的网络资源关于docker desktop迁移都是旧版本的,即4.30版本之前。在4.30版本及以后,在运行wsl -l -v时只有docker-desktop只有这一项…...
单向函数、单向陷门函数、困难问题
1、单向函数 设函数 yf(x) , 对于给定的x,计算出y很容易;对于给定的y,计算出x很难。 2、单向陷门函数 设函数 yf(x) ,且f有陷门, 对于给定的x,计算出y很容易;对于给定的y&#…...
MYSQL 小猫钓鱼 - 猫王争霸之〈主从设计〉
在美丽的森林中,小猫们的钓鱼大赛依旧热闹非凡,而 “猫王争霸” 的竞争也越来越激烈。随着时间的推移,越来越多的动物们开始关注这场有趣的比赛,对鱼表数据的查询请求也急剧增加。 一、请求压力剧增 花猫看着鱼表发愁道…...
arcgis坐标系问题
2000数据框的工程只能打开2000坐标系的矢量数据和栅格数据(影像图),如果打开80的数据则会投影错误,出现较大偏差。 解决方案:80数据框打开80数据,2000数据库打开2000数据。...
ubuntu 24.04中安装 Easyconnect,并解决版本与服务器不匹配问题
下载安装包 下载地址 https://software.openkylin.top/openkylin/yangtze/pool/all/ 页面搜索 easyconnect 选择 easyconnect_7.6.7.3.0_amd64.deb安装 sudo dpkg --install easyconnect_7.6.7.3.0_amd64.deb卸载 sudo dpkg --remove easyconnect出现的问题 安装以后第…...
【软考】RUP相关考点总结
RUP,是一个重量级过程,提供一个在线指导,为所有方面提供指导方针。 关于RUP(统一软件开发过程)的9个核心工作流,如果考试中出现,可能会以以下几种方式进行考察: 定义和描述ÿ…...
PostgreSQL 删除角色
我们在使用 PostgreSQL 数据库的时候,经常会遇到这样的场景,就是某个角色,现在不需要了,我们需要删除。但是在删除的时候又提示你无法删除角色。下面看一下具体的情况。 DROP USER cloud_readonly > ERROR: role "cloud…...
华为HCIP —— QinQ技术实验配置
一、QinQ的概述 1.1QinQ的概念 QinQ(802.1Q in 802.1Q)技术是一项扩展VLAN空间的技术,通过在原有的802.1Q报文基础上再增加一层802.1Q的Tag来实现。 1.2QinQ封装结构 QinQ封装报文是在无标签的以太网数据帧的源MAC地址字段后面加上两个VL…...
全网最简单的GraphRAG讲解,包你懂
一、什么是 GraphRAG? GraphRAG(基于图的检索增强生成)是在传统 RAG 方法的基础上,引入了图数据结构的新型方法。它利用大语言模型的强大自然语言理解能力,从非结构化文本中抽取实体和关系,构建知识图谱&a…...
rust 压缩解压库flate2保姆级教程
前言 flate2 是 Rust 中用于处理 gzip 和其他压缩格式的库。以下是 flate2 的主要 API 和用法说明。 依赖添加 在你的 Cargo.toml 中添加依赖: [dependencies] flate2 "1.0.34"主要模块 flate2::write:用于压缩数据的写入器。flate2::re…...
秒杀优化(异步秒杀,基于redis-stream实现消息队列)
目录 秒杀优化一:异步秒杀1:思路2:实现 二:redis实现消息队列1:什么是消息队列2:基于list结构实现消息队列3:基于pubsub实现消息队列4:基于stream实现消息队列5:stream的…...
Node.js——fs模块-文件读取
1、文件读取:通过程序从文件中去除其中的数据 2、方法 方法 说明 readFile 异步读取 readFileSync 同步读取 createReadStrean 流式读取 3、readFile 异步读取 语法: 本文的分享到此结束,欢迎大家评论区一同讨论学习,下一…...
深入理解 ZooKeeper:分布式协调服务的核心与应用
一、引言 随着互联网技术的飞速发展,分布式系统的规模和复杂性不断增加。在分布式环境中,各个节点之间需要进行高效的协调和通信,以确保系统的正常运行。ZooKeeper 正是为了解决分布式系统中的协调问题而诞生的一款开源软件。它提供了一种简单…...
你竟然还不了解 LDAP?
目录 什么是 LDAP LDAP 的工作原理 LDAP 的数据模型 LDAP 操作 LDAP 的使用场景 常见的 LDAP 服务器 小结 什么是 LDAP LDAP(Lightweight Directory Access Protocol,轻量级目录访问协议)是用于访问和管理目录服务的一种开放协议&…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看
文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...
Oracle11g安装包
Oracle 11g安装包 适用于windows系统,64位 下载路径 oracle 11g 安装包...
c# 局部函数 定义、功能与示例
C# 局部函数:定义、功能与示例 1. 定义与功能 局部函数(Local Function)是嵌套在另一个方法内部的私有方法,仅在包含它的方法内可见。 • 作用:封装仅用于当前方法的逻辑,避免污染类作用域,提升…...
华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)
题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...
MySQL的pymysql操作
本章是MySQL的最后一章,MySQL到此完结,下一站Hadoop!!! 这章很简单,完整代码在最后,详细讲解之前python课程里面也有,感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...
自然语言处理——文本分类
文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益(IG) 分类器设计贝叶斯理论:线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别, 有单标签多类别文本分类和多…...
