每日一题---OJ题: 链表的回文结构

片头

嗨! 小伙伴们,大家好! 今天我们来一起学习这道OJ题--- 链表的回文结构

嗯...这道题好像不是很难,我们来分析分析

举个例子:

我们可以看到,上图中的两个链表都是回文结构: 即链表的回文结构是指一个链表中的结点值从前往后读和从后往前读都是一样的结构。也就是说,链表的顺序是回文的。

例如,以下链表是回文结构: 1 -> 2 -> 3 -> 2 -> 1

而以下链表不是回文结构: 1 -> 2 -> 3 -> 4 -> 5

那我们怎么判断是不是链表的回文结构呢?

思路1 : 我们可以先找到链表的中间结点,然后反转从这个中间结点开始一直到最后一个结点,并且将反转后的新结点返回,最后定义两个变量,分别去遍历链表的头结点和新结点

比如:

我们定义2个变量,A表示指向链表的头结点(第一个结点),rmid 表示指向反转链表返回的新结点

我们让 A 和 rmid 指向的结点依次比较,如果中途 A 指向结点的值不等于rmid结点指向的值,那么直接退出循环,返回 false;如果比较到 A 和 rmid 都为, 那么返回 true

第一次比较:  A 和 rmid 指向的结点的数据域都相等, 那么指针 A 向后走一步, 指针 rmid 向后走一步

第二次比较: A 和 rmid 指向的结点的数据域都相等, 那么指针 A 向后走一步, 指针 rmid 向后走一步

第三次比较: rmid指针指向NULL, 退出循环, 返回 true 

我们查找链表的中间结点的代码如下:

    //找出中间结点struct ListNode* Find(struct ListNode* head){struct ListNode* fast = head;            //fast指针指向第一个结点struct ListNode* slow = head;            //slow指针指向第一个结点while(fast && fast->next){            // 当 fast 并且 fast->next 不为空时,进入循环                   slow = slow->next;                //slow指针每次走一步fast = fast->next->next;          //fast指针每次走两步}return slow;                          //返回slow指针指向的结点,就是中间结点}

具体的关于链表的中间结点讲解在这里哦, 小伙伴们可以点击查看:  链表的中间结点 (注意: 点击蓝色字体就可以跳转到相应的文章哦!)

我们找到链表的中间结点后,我们就可以反转从这个中间结点开始一直到最后一个结点

反转链表的代码如下:

    //反转链表struct ListNode* Reverse(struct ListNode* head){struct ListNode* n1 = nullptr;            //定义一个n1指针指向NULLstruct ListNode* n2 = head;               //定义一个n2指针指向头结点struct ListNode* n3 = head->next;         //定义一个n3指针指向头结点的下一个结点while(n2 != nullptr){                     //判断n2是否为空n2->next = n1;                        //如果n2非空,就把n2的next指针指向n1n1 = n2;                              //把n2赋给n1n2 = n3;                              //把n3赋给n2if(n3){                               //如果n3非空,就让n3指向n3的下一个结点n3 = n3->next;}}return n1;                                //最后n2和n3都为空,n1恰好是新链表的头结点}

具体的关于反转链表的讲解可以戳这里哦,小伙伴们可以点击查看:  反转链表 (注意: 点击蓝色字体就可以跳转到相应的文章哦!)

好啦,准备工作做好了以后,我们就可以在题目所给的方法里面写代码啦!

首先,我们要定义一个结点指针,用来接收返回过来的中间结点;  其次,我们需要定义另外一个结点指针,用来接收反转链表后的新结点。

将两个指针所指向的结点进行比较,如果它们的数据域不同,说明链表不是回文结构, 则跳出循环, 返回 false ; 如果数据域相同,那么两个指针同时往后走一步,继续比较下一个结点,直到其中一个指针指向NULL, 说明链表是回文结构, 返回 true。

整体代码如下:

class PalindromeList {public://找出中间结点struct ListNode* Find(struct ListNode* head) {struct ListNode* fast = head;            //fast指针指向第一个结点struct ListNode* slow = head;            //slow指针指向第一个结点// 当 fast 并且 fast->next 不为空时,进入循环while (fast && fast->next) {         slow = slow->next;         //slow指针每次走一步fast = fast->next->next;   //fast指针每次走两步}return slow;                   //返回slow指针指向的结点,就是中间结点}//反转链表struct ListNode* Reverse(struct ListNode* head){//定义一个n1指针指向NULLstruct ListNode* n1 = nullptr;           //定义一个n2指针指向头结点struct ListNode* n2 = head;              //定义一个n3指针指向头结点的下一个结点struct ListNode* n3 = head->next;while(n2 != nullptr){       //判断n2是否为空n2->next = n1;          //如果n2非空,就把n2的next指针指向n1n1 = n2;                //把n2赋给n1n2 = n3;                //把n3赋给n2if(n3){                 //如果n3非空,就让n3指向n3的下一个结点n3 = n3->next;}}return n1;                 //最后n2和n3都为空,n1恰好是新链表的头结点}bool chkPalindrome(ListNode* A) {//定义mid指针,用来接收中间结点struct ListNode* mid = Find(A);    //定义r指针,用来接收将链表反转后的新结点 struct ListNode* r = Reverse(mid); ListNode* pcur = A;//当两个指针都不为空时,进入while循环while (pcur && r) {//如果两个指针指向的结点的数据域不相同,说明链表不是回文结构,那么返回 falseif (pcur->val != r->val) {return false;}//如果两个指针指向的结点数据域相同,那么继续比较下一个结点pcur = pcur->next;r = r->next;}//其中一个指针走向NULL,说明是链表回文结构,返回 truereturn true;}
};

片尾

今天我们学习了一道OJ题: 链表的回文结构,里面涉及了查找链表的中间结点以及反转链表等知识,希望看完这篇文章的能对友友们有所帮助 !  !  !

点赞收藏加关注 !   !   !

谢谢大家 !   !   !

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

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

相关文章

详细UI色彩搭配方案分享

UI 配色是设计一个成功的用户界面的关键之一。UI 配色需要考虑品牌标志、用户感受、应用程序的使用场景,这样可以帮助你创建一个有吸引力、易于使用的应用程序。本文将分享 UI 配色的相关知识,帮助设计师快速构建 UI 配色方案,以满足企业的需…

老挝公司注册

随着昆明和万象之前的中老铁路开通,进一步加强了老挝与中国之前的经济联系。中老昆万铁路是老挝“陆锁国”变“陆联国”战略深入对接“一带一路”倡议的纽带,是老挝现代化基础设施建设的一个重要里程碑,将极大促进老挝国家经济社会发展。 如…

EI级 | Matlab实现VMD-TCN-LSTM-MATT变分模态分解卷积长短期记忆神经网多头注意力多变量时间序列预测

EI级 | Matlab实现VMD-TCN-LSTM-MATT变分模态分解卷积长短期记忆神经网多头注意力多变量时间序列预测 目录 EI级 | Matlab实现VMD-TCN-LSTM-MATT变分模态分解卷积长短期记忆神经网多头注意力多变量时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 1.Matlab实…

好用、可靠有安全的企业局域网文件传输工具

在当今商业环境中,企业对于快速、安全的局域网(LAN)文件传输解决方案的需求不断攀升。选择恰当的工具对提升工作效率和保障数据安全至关重要,同时还能降低潜在的信息泄露风险。以下是企业在挑选局域网文件传输解决方案时应考虑的关键因素及其重要性的详细…

回文链表leecode

回文链表 偶数情况奇数情况 回文链表leecode 偶数情况 public boolean isPalindrome(ListNode head) {if (head null) {return true;}ListNode fast head;ListNode slow head;while (fast ! null && fast.next ! null) {fast fast.next.next;slow slow.next;}//反…

selenium_定位输入框并输入值_id

定位id号 from time import sleepfrom selenium import webdriver# 获取浏览器对象 driver webdriver.Edge() # 打开 url url r"C:\Users\黄永生\Desktop\软件测试\tpshop\web自动化_day01_课件笔记资料代码\02_其他资料\注册A.html" driver.get(url) # 查找元素 用…

如何合理利用多个中国大陆小带宽服务器?

我们知道在中国大陆带宽单价非常昂贵,一个1Mbps 带宽的机子一年就得卖好几百人民币,这是不值当的,当然我们可以去低价漂阿里云、腾讯云的轻量服务器,99包年,但是带宽太小很难崩。 所以,我们必须构建一个能够…

07节-51单片机-矩阵键盘

文章目录 1矩阵键盘原理2.扫描的概念3.弱上拉4.实战-实现矩阵键盘对应按钮按下显示对应值4.1配置代码模板 5.键盘锁 1矩阵键盘原理 在键盘中按键数量较多时,为了减少I/O口的占用,通常将按键排列成矩阵形式 采用逐行或逐列的“扫描”,就可以读…

回归预测 | Matlab基于RIME-SVR霜冰算法优化支持向量机的数据多输入单输出回归预测

回归预测 | Matlab基于RIME-SVR霜冰算法优化支持向量机的数据多输入单输出回归预测 目录 回归预测 | Matlab基于RIME-SVR霜冰算法优化支持向量机的数据多输入单输出回归预测预测效果基本描述程序设计参考资料 预测效果 基本描述 1.Matlab基于RIME-SVR霜冰算法优化支持向量机的数…

【AI工具之Prezo如何自动生成PPT操作步骤】

先说优缺点: 最大的优点就是免费(但说实话功能和体验方面很弱)支持中文提问(最好用英文),智能生成图文(但是只能生成英文内容)可以AI生成图片,图片很精美酷炫&#xff0…

Java学习-详述main方法、可变参数、数组的工具类、二维数组

详述main方法 【1】main方法:程序的入口,在同一个类中,如果有多个方法,那么虚拟机就会识别main方法,从这个方法作为程序的入口 【2】main方法格式严格要求: public static void main(String[] args){} p…

bonding原理分析和问题排查

bonding原理 发送端: 使用网卡bond3模式(广播模式BOND_MODE_BROADCAST)将报文从两个网卡同时发出,无需修改报文。 接收端: 根据发送节点时间的链路通断状态,接收端设置一条线路为活动线,另一条…

diffusion model 简单demo

参考自: Probabilistic Diffusion Model概率扩散模型理论与完整PyTorch代码详细解读 diffusion 简单demo 扩散模型之DDPM 核心公式和逻辑 q_x 计算公式,后面会用到: 推理: 代码 import matplotlib.pyplot as plt import nump…

【devops】 阿里云挂载云盘 | 扩展系统硬盘 | 不重启服务器增加硬盘容量

扩容分区和文件系统(Linux) 文档地址 https://help.aliyun.com/zh/ecs/user-guide/extend-the-partitions-and-file-systems-of-disks-on-a-linux-instance?spm5176.smartservice_service_robot_chat_new.help.dexternal.4ac4f625Ol66kL#50541782adxmp…

C++ UML 类图介绍与设计

1 类图概述 UML(Unified Modeling Language),即统一建模语言,是用来设计软件的可视化建模语言。它的特点是简单、统一、图形化、能表达软件设计中的动态与静态信息。UML从目标系统的不同角度出发,定义了用例图、类图、对象图、状态图、活动图…

高效率改写文章,一键智能改写工具有妙招

如今,写作已经成为人们日常生活中不可或缺的一部分。无论是职场人士撰写工作报告,还是专业的作者创作文章,都离不开对文字的润色和改写。然而,随着工作量与时间压力的增加,如何在保证质量的前提下提高文章改写的效率成…

关于GDAL计算图像坐标的几个问题

关于GDAL计算图像坐标的几个问题_gdal读取菱形四角点坐标-CSDN博客 这篇文章写的很好,讲清楚了图像行列号与图像点坐标(x,y)对应关系,以及图像行列号如何转为地理坐标的,转载一下做个备份。 1.关于GDAL计算图像坐标的…

数据库服务的运行与登录

打开数据库服务 数据库服务: SQL Server(MSSQLServer) 运行在服务器端的应用程序, 提供数据的存储 / 处理和事务等在使用DBMS的客户端之前必须首先打开该服务 客户端连接到服务器 关于客户端 / 服务器端的说明 客户端 : 数据库管理系统(DBMS), 应用程序服务器端 : 安装的数据…

通过本机电脑远程访问路由器loopback的ip

实验拓扑图 本机电脑增加路由信息 正常设置telnet用户,然后通过本地电脑telnet 软件ensp中的设备,尝试是否可以正常访问即可 测试通过本地电脑可以正常访问ensp里面设备的loopback的ip地址了 最重要的一点是本机需要增加一条路由route add ip mask 下…

户外旅行摄影手册,旅游摄影完全攻略

一、资料前言 本套旅游摄影资料,大小295.47M,共有9个文件。 二、资料目录 《川藏线旅游摄影》杨桦.彩印版.pdf 《户外摄影指南》(Essential.Guide.to.Outdoor.photography.amateur)影印版.pdf 《旅行摄影大师班》(英)科尼什.扫描版.PDF 《旅行摄影…