单链表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;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/462970.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

整理 【 DBeaver 数据库管理工具 】的一些基础使用

目录 连接设置切换工作空间SQL编辑器&#xff08;写sql语句&#xff09;打开方式新建查询&#xff08;sql编辑器&#xff09;打开写的 sql 查询&#xff08;项目浏览器&#xff09; 备份sql文件查看历史执行语句自动保存sql语句的文件&#xff08;编辑器&#xff09;关闭自动生…

Android Studio 依赖仓库地址

在Android Studio进行开发时&#xff0c;会遇到依赖库下载慢或者老项目使用的依赖库找不到的问题&#xff0c;折腾了两天&#xff0c;终于找到解决方法&#xff0c;使用 阿里云云效Maven&#xff0c;地址&#xff1a;仓库服务https://developer.aliyun.com/mvn/guide &#xff…

51单片机教程(五)- LED灯闪烁

1 项目分析 让输入/输出口的P1.0或P1.0~P1.7连接的LED灯闪烁。 2 技术准备 1、C语言知识点 1 运算符 1 算术运算符 #include <stdio.h>int main(){// 算术运算符int a 13;int b 6;printf("%d\n", ab); printf("%d\n", a-b); printf("%…

MySQL日志——针对实习面试

目录 MySQL日志MySQL有哪些日志&#xff1f;请解释一下MySQL的二进制日志&#xff08;Binlog&#xff09;的作用&#xff1f;复制&#xff08;Replication&#xff09;数据恢复&#xff08;Point-in-Time Recovery&#xff09; Binlog日志的三种格式是什么&#xff1f;如何使用…

STM32 HAL库 SPI驱动1.3寸 OLED屏幕

目录 参考硬件引脚与接线 点亮屏幕CubeMX 配置OLED 驱动程序代码 参考 基于STM32F103C8T6最小系统板HAL库CubeMX SPI驱动7针 OLED显示屏&#xff08;0.96寸 1.3寸通用&#xff09;0.96 oled HAL库驱动 SPI STM32SPI驱动0.96/1.3寸 OLED屏幕&#xff0c;易修改为DMA控制STM32驱…

qt QStatusBar详解

1、概述 QStatusBar是Qt框架提供的一个小部件&#xff0c;用于在应用程序窗口底部显示状态信息。它可以显示一些固定的文本和图标&#xff0c;并且可以通过API动态更新显示内容。QStatusBar通常是一个水平的窗口部件&#xff0c;能够显示多行文本内容&#xff0c;非常适合用于…

h5st参数解析

前言 之前4.8卡我&#xff0c;感觉过了&#xff0c;但是又好像失败了&#xff0c;所以这篇博客憋着没写&#xff0c;这次再次搞了一下&#xff0c;这次弄起来感觉挺简单的啊。 分析 1 20241102203105966; 2 fhhv55ehre91k4l8; 3 f06cc; 4 tk03w…

clickhouse运维篇(二):多机器手动部署ck集群

熟悉流程并且有真正部署需求可以看一下我的另一篇简化部署的文章&#xff0c;因为多节点配置还是比较麻烦的先要jdk、zookeeper&#xff0c;再ck&#xff0c;还有各种配置文件登录不同机器上手动改配置文件还挺容易出错的。 clickhouse运维篇&#xff08;三&#xff09;&#x…

导航栏小案例

实现类似于这样的效果 <!DOCTYPE html> <html><head><meta charset"utf-8"><title>导航栏</title><style>*{margin: 0;padding: 0;}.div1{width: 100%;height: 60px;/* border: 1px solid blue; */background-color:rgb(…

ASP .NET CORE 6 在项目中集成WatchDog开源项目

概念 WatchDog是一个开源的项目&#xff0c;可以实现对.Net 应用程序和API实现实时应用日志和性能监控平台。可以实现实时记录和查看应用程序中的消息、事件、HTTP请求和响应&#xff0c;以及运行时捕获的异常&#xff0c;有效帮助开发人员去排查应用异常&#xff0c;提升开发效…

四、k8s快速入门之Kubernetes资源清单

kubernetes中的资源 ⭐️ k8s中所有的内容都抽象为资源&#xff0c;资源实列化之后&#xff0c;叫做对象 1️⃣名称空间级别 ⭐️ kubeadm在执行k8s的pod的时候会在kube-system这个名称空间下执行&#xff0c;所以说当你kubectl get pod 的时候是查看不到的查看的是默认的po…

无人机之集群控制方法篇

无人机的集群控制方法涉及多个技术和策略&#xff0c;以确保多架无人机能够协同、高效地执行任务。以下是一些主要的无人机集群控制方法&#xff1a; 一、编队控制方法 领航-跟随法&#xff08;Leader-Follower&#xff09; 通过设定一架无人机作为领航者&#xff08;长机&am…

给大家推荐一本书《GPT时代人类再腾飞》

大家好&#xff0c;我是袁庭新。给大家推荐一本书——《GPT时代人类再腾飞》。 先给大家介绍一位顶级大佬——里德霍夫曼。他是著名互联网企业家&#xff0c;领英联合创始人&#xff1b;知名风险投资者&#xff0c;Open AI早期投资人&#xff1b;《纽约时报》畅销书作者、播客…

法律智能助手:开源NLP系统助力法律文件高效审查与检索

一、系统概述 思通数科AI平台是一款融合了自然语言处理和多标签分类技术的开源智能文档分类工具&#xff0c;特别适用于法律行业。平台采用深度学习的BERT模型来进行特征提取与关系抽取&#xff0c;实现了精准的文档分类和检索。用户可以在线训练和标注数据&#xff0c;使系统…

redis模板的应用:自定义redisTemplate序列化规则 (RedisTemplate和StringRedisTemplate)

文章目录 引言I 基础知识redis对key和value使用序列化方式RedisTemplate<Object, Object>自定义redisTemplate序列化规则RedisTemplate<String, String>II 存储自定义对象redisTemplate存储自定义对象StringRedisTemplate存储自定义对象引言 StringRedisTemplate只…

SQL之排名窗口函数RANK()、ROW_NUMBER()、DENSE_RANK() 和 NTILE() 的区别(SQL 和 Hive SQL 都支持)

现有一张student 表&#xff0c;表中包含id、uname、age、score 四个字段&#xff0c;如下所示&#xff1a; 该表的数据如下所示&#xff1a; 一、ROW_NUMBER() 1、概念 ROW_NUMBER() 为结果集中的每一行分配一个唯一的连续整数&#xff0c;编号从 1 开始。‌ 该函数按照指…

【开源免费】基于SpringBoot+Vue.JS网上超市系统(JAVA毕业设计)

本文项目编号 T 037 &#xff0c;文末自助获取源码 \color{red}{T037&#xff0c;文末自助获取源码} T037&#xff0c;文末自助获取源码 目录 一、系统介绍二、演示录屏三、启动教程四、功能截图五、文案资料5.1 选题背景5.2 国内外研究现状5.3 可行性分析 六、核心代码6.1 查…

mac电脑设置crontab定时任务,以及遇到的问题解决办法

crontab常用命令 crontab -u user&#xff1a;用来设定某个用户的crontab服务&#xff1b; crontab file&#xff1a;file是命令文件的名字,表示将file做为crontab的任务列表文件并载入crontab。如果在命令行中没有指定这个文件&#xff0c;crontab命令将接受标准输入&#xf…

基于vue+neo4j 的中药方剂知识图谱可视化系统

前言 历时一周时间&#xff0c;中药大数据R02系统中药开发完毕&#xff0c;该系统通过scrapy工程获取中药数据&#xff0c;使用python pandas预处理数据生成知识图谱和其他相关数据&#xff0c;利用vuespringbootneo4jmysql 开发系统&#xff0c;具体功能请看本文介绍。 简要…

Qt的程序如何打包详细教学

生成Release版的程序 在打包Qt程序时&#xff0c;我们需要将发布程序需要切换为Release版本&#xff08;Debug为调试版本&#xff09;&#xff0c;编译器会对生成的Release版可执行程序进行优化&#xff0c;使生成的可执行程序会更小。 debug版本 debug版本是一种开发过程中的…