单链表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,轻量级目录访问协议)是用于访问和管理目录服务的一种开放协议&…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...
STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
五子棋测试用例
一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏,有着深厚的文化底蕴。通过将五子棋制作成网页游戏,可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家,都可以通过网页五子棋感受到东方棋类…...
C# winform教程(二)----checkbox
一、作用 提供一个用户选择或者不选的状态,这是一个可以多选的控件。 二、属性 其实功能大差不差,除了特殊的几个外,与button基本相同,所有说几个独有的 checkbox属性 名称内容含义appearance控件外观可以变成按钮形状checkali…...
解析“道作为序位生成器”的核心原理
解析“道作为序位生成器”的核心原理 以下完整展开道函数的零点调控机制,重点解析"道作为序位生成器"的核心原理与实现框架: 一、道函数的零点调控机制 1. 道作为序位生成器 道在认知坐标系$(x_{\text{物}}, y_{\text{意}}, z_{\text{文}}…...
