当前位置: 首页 > news >正文

回文链表(快慢指针解法之在推进过程中反转)

归纳编程学习的感悟,
记录奋斗路上的点滴,
希望能帮到一样刻苦的你!
如有不足欢迎指正!
共同学习交流!
🌎欢迎各位→点赞 👍+ 收藏⭐ + 留言​📝

抱怨深处黑暗,不如提灯前行!

 

题目描述:

给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。

示例 1:

输入:head = [1,2,2,1]
输出:true

示例 2:

输入:head = [1,2]
输出:false

提示:

  • 链表中节点数目在范围[1, 105] 内
  • 0 <= Node.val <= 9

思路推导

判断该链表是否为回文链表,数据范围node.val<=9,节点数量∈[1,10^5]node.val <= 9, 节点数量 ∈ [1,10^5]node.val<=9,节点数量∈[1,10^5 ]

可选方案1:转数字,判断是否为回文数
可选方案2:转字符串,判断是否为回文串
但这样做就没有利用到链表自身的性质,因此不是最合适的解法。
根据「206.反转链表」的思路,可以在完成「链表前半部分的反转」之后,通过双指针指向前半部分的头结点和后半部分链表的头结点,每次推进一步并判断数值是否相等。
但这存在「奇数节点个数的链表」和「偶数节点个数的链表」的前半部分和后半部分划分上的不同的问题。
情况分析
回文链表必然会存在「奇数个节点」的链表和「偶数个节点」的链表。

对于长度为奇数的回文链表
1->2->3->2->1,长度为5的链表,那么从回文中心3向左右两侧出发,会遍历得到相同的数字序列。
对于偶数长度的回文链表:
1->2->2->1,长度为4的链表,如果回文,那么从第2和第3个节点出发,向两侧扫描,可以得到相同的数字序列。
因此,假设节点个数为n

奇数链表:

回文中心为:(n+1)/2个节点
回文边界为:(n+1)/2 - 1,(n+1)/2 + 1
偶数链表:

没有回文中心
回文边界:n/2和n/2 + 1
之后可以通过「统计节点个数」->「对奇偶链表需要翻转的节点个数分别判断完成前半部分反转」->「从前半部分链表和后半部分链表的头结点向两侧扫描推进判断数字是否相同」的方法来判断回文链表。

但目前这样的考虑过于复杂了,因为实际上我们无需计算节点个数,只需要确定链表中间节点的位置即可。「确定链表中间节点的位置」的方法通常使用快慢指针法。

示例分析
设计双指针slow = head, fast = head
「奇数链表」和「偶数链表」最终确定的中间节点不一致,我们可以先确定「链表中间节点位置」,再「反转前半部分的链表」;也可以考虑在slow指针推进过程中完成「局部反转」,这样到达「中间位置节点」时恰好完成了前半部分的反转。

  • 偶数链表的示例分析:
局部翻转还需要的变量pre以及变量初始化:
设计pre = null, slow = fast = head;
当前循环条件未知。
每次循环,slow指针每次前进一步,就翻转局部链表,fast指针前进两步。
偶数节点情况:
初始化:
null 1 -> 2 -> 2 -> 1 -> null^   ^
pre slow,fast
---------------------------------
第1轮循环
null<- 1   2 ->  2 -> 1 -> null^   ^ 	 ^pre  slow fast
---------------------------------
第2轮循环:
null<- 1 <- 2   2-> 1-> null^	^		 ^pre  slow 	fast
第二次循环结束后,就已经完成了前半部分链表的反转,
pre指向前半部分链表的第一个元素。
slow到达「中间节点的第二个节点」。
slow指针指向后半部分链表的第一个元素。
偶数链表的循环退出条件是 fast == null
  • 奇数链表的示例分析:

奇数链表模拟:
初始化
null 1 -> 2 -> 3 -> 2 -> 1 -> null^   ^
pre  slow,fast
第一轮循环
null<- 1	2 -> 3 -> 2 -> 1 -> null^    ^	 ^pre  slow fast第二轮循环:
null<- 1 <- 2 	3 -> 2 -> 1 -> null^	^		  ^pre slow		fast
第二轮循环结束后,slow到达「链表中间节点」位置。
循环退出条件是 fast.next == null 
循环退出时
fast = 链表最后一个元素
pre 指向前部分链表的第一个元素
slow 指针指向后部分链表的第一个元素。
需要特殊处理:即将slow指针向后推进一位,
以保证和「偶数链表」相同,slow指针指向后半部分回文链表的第一个元素。
  • 抽取循环结束时的共性:

pre指向前半部分链表的第一个元素。
slow指针经过处理后,指向后半部分链表的首个元素
循环退出条件:
        对于奇数链表为fast.next == null
        对于偶数链表为fast==null

  • 通过「奇数链表」和「偶数链表」的示例分析得到伪代码:

循环开始:
1. 变量初始化 
双指针赋值slow = head, fast = head, 
局部旋转前一个变量指针pre = null
局部翻转需要保存的下一个节点 tmp = null 
2. 双指针推进循环
循环条件(fast != null && fast.next != null){2.1 快指针每次推进两步。2.2 慢指针通过「局部反转」的方式进行指针的推进。
}
3.循环结束后的情况分析:3.1 偶数链表循环结束后,fast == null,pre指向前半部分第一个回文数slow指向后半部分第一个回文数3.2 奇数链表循环结束后,fast !=null, fast.next == nullpre指向前半部分第一个回文数slow指向后半部分第一个节点(链表中间节点)。为使得一致,slow指针需要指向第一个回文数需要将slow向前推进一步
因此,如果fast != null,将slow指针推进一步。
4. 此时pre指向前半部分链表第一个回文数,slow指向后半部分链表第一个回文数。
循环判断:
循环条件:pre!= null || slow.next != null
向两边同时推进pre和slow,比较pre.val和slow.val是否相等,
如果pre.val != slow.val,说明不是回文数,返回false。
当pre和slow都推进到链表末尾,说明每个数都相等,返回true。

代码实现:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode LNode;
bool isPalindrome(struct ListNode* head) {LNode*fast;LNode*slow;fast=head;slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}LNode *temp,*pre,*cur;pre=NULL;cur=slow;while(cur){temp=cur->next;cur->next=pre;pre=cur;cur=temp;}LNode*p;p=head;while(pre&&p){if(p->val!=pre->val){break;}p=p->next;pre=pre->next;}if(p==NULL||pre==NULL){return true;}else{return false;}
}

复杂度分析:

时间复杂度:O(n),双指针扫描链表一遍O(n),局部反转时间复杂度O(1),回文数比较时间复杂度O(n)。
空间复杂度:O(1),指针只占用了常量的空间。

相关文章:

回文链表(快慢指针解法之在推进过程中反转)

归纳编程学习的感悟&#xff0c; 记录奋斗路上的点滴&#xff0c; 希望能帮到一样刻苦的你&#xff01; 如有不足欢迎指正&#xff01; 共同学习交流&#xff01; &#x1f30e;欢迎各位→点赞 &#x1f44d; 收藏⭐ 留言​&#x1f4dd;抱怨深处黑暗&#xff0c;不如提灯前行…...

深度剖析:为什么 Spring 和 IDEA 都不推荐使用 @Autowired 注解

目录 依赖注入简介 Autowired 注解的优缺点 Spring 和 IDEA 不推荐使用 Autowired 的原因 构造器注入的优势 Autowired 注解的局限性 可读性和可测试性的问题 推荐的替代方案 构造器注入 Setter 注入 Java Config Bean 注解 项目示例&#xff1a;Autowired vs 构造器…...

【接口自动化_05课_Pytest接口自动化简单封装与Logging应用】

一、关键字驱动--设计框架的常用的思路 封装的作用&#xff1a;在编程中&#xff0c;封装一个方法&#xff08;函数&#xff09;主要有以下几个作用&#xff1a;1. **代码重用**&#xff1a;通过封装重复使用的代码到一个方法中&#xff0c;你可以在多个地方调用这个方法而不是…...

信息学奥赛初赛天天练-14-阅读程序-字符数组、唯一分解定理应用

更多资源请关注纽扣编程微信公众号 1 2019 CSP-J 阅读程序1 (程序输入不超过数组或字符串定义的范围&#xff1b;判断题正确填√,错误填&#xff1b;除特殊说明外&#xff0c;判断题1.5分&#xff0c;选择题3分&#xff0c;共计40分) 1 输入的字符串只能由小写字母或大写字母组…...

K210 数字识别 笔记

一、烧写固件 连接k210开发板&#xff0c;点开烧录固件工具&#xff0c;选中固件&#xff0c;并下载 二、模型训练 网站&#xff1a;MaixHub 1、上传文件 2、开始标记数据 添加9个标签&#xff0c;命名为1~9&#xff0c;按键盘w开始标记&#xff0c;键盘D可以下一张图片&…...

人脸检测--FaceNet(四)

FaceNet 是一个由 Google 研究团队开发的人脸识别系统&#xff0c;它基于深度学习技术&#xff0c;可以实现高精度的人脸识别、验证和聚类任务。FaceNet 通过学习直接从图像像素到人脸嵌入的映射&#xff0c;使得它在各种人脸识别任务中表现出色。下面是对 FaceNet 的详细介绍&…...

Android性能优化方案

1.启动优化&#xff1a; application中不要做大量耗时操作,如果必须的话&#xff0c;建议异步做耗时操作2.布局优化&#xff1a;使用合理的控件选择&#xff0c;少嵌套。&#xff08;合理使用include,merge,viewStub等使用&#xff09;3.apk优化&#xff08;资源文件优化&#…...

视频监控平台AS-V1000 的场景管理,一键查看多画面视频的场景配置、调用、管理(一键浏览多路视频)

目录 一、场景管理的定义 二、场景管理的功能和特点 1、功能 &#xff08;1&#xff09;场景配置 &#xff08;2&#xff09;实时监控 &#xff08;3&#xff09;权限管理 2、特点 三、AS-V1000的场景配置和调用 1、场景配置 &#xff08;1&#xff09;实时视频预览 …...

微服务架构五大设计模式详解,助你领跑行业

微服务架构设计模式详解(5种主流模式) 微服务架构 微服务&#xff0c;一种革命性的架构模式&#xff0c;主张将大型应用分解为若干小服务&#xff0c;通过轻量级通信机制互联。每个服务专注特定业务&#xff0c;具备独立部署能力&#xff0c;轻松融入生产环境&#xff0c;为系…...

【problem】解决EasyExcel导出日期数据显示为#####问题

前言 在使用EasyExcel进行数据导出时&#xff0c;你可能遇到日期或其他数据在Excel中显示为“#######”的情况&#xff0c;这通常是因为列宽不足以展示单元格内的全部内容。本文将指导你如何通过简单的步骤解决这一问题&#xff0c;并确保导出的Excel文件自动调整列宽或直接指…...

Pytest用例自定义 - 重复、并行、串行

简介&#xff1a;面对快速迭代和持续交付的需求&#xff0c;提高测试效率变得至关重要。并行测试因其显著的时间节省优势而备受青睐。然而&#xff0c;并非所有测试都适合并行执行。在某些情况下&#xff0c;串行执行是必要的&#xff0c;以确保测试的正确性和稳定性。本文将探…...

前端项目上线

目录 1项目打包 2本地服务器部署 2.1具体操作步骤 2.2解决刷新 404 问题 2.3请求无法发送问题 3nginx 服务器部署 3.2nginx 配置代理练习 安装nginx nginx部署启动项目 3.3nginx 部署前端项目 4云服务器部署 本地资源上传 配置服务器与nginx 1项目打包 ●我…...

redis基本数据结构与应用

文章目录 概要String结构Hash结构List结构Set结构Zset结构bitmap位图类型geo地理位置类型其他常用命令 概要 redis常用的5种不同数据结构类型之间的映射如下&#xff1a; 结构类型结构存储的值结构的读写能力STRING可以是字符串、整数或者浮点数key-value形式&#xff1b;对整…...

Python pands使用引擎实现excel条件格式

截至我的知识更新日期&#xff08;2023年&#xff09;&#xff0c;Pandas 库本身并不直接支持Excel条件格式。Pandas 是一个强大的Python数据分析库&#xff0c;它主要用于数据分析和操作&#xff0c;而不是用于创建或编辑Excel文件的格式。 然而&#xff0c;你可以使用 openp…...

基于 vuestic-ui 实战教程 - 登录篇

1. 简介 登录做为一个系统的门面&#xff0c;也是阻挡外界的一道防线&#xff0c;那在vuestic-ui中如何做登录功能呢。在这里就之间沿用初始版本的Login页面&#xff0c;作为一个演示模板&#xff0c;后续需要改进的读者可以在此篇文章的基础上修改。 2. 登录接口相关api 与 t…...

SAPUI5基础知识2 - 手动创建一个SAPUI5的项目

1. 前言 在本篇文章中&#xff0c;我们将手动一步一步建立出第一个SAPUI5的 ‘Hello World!’ 项目。 2. 步骤详解 2.1 在BAS中建立Dev Space 进入SAP Business Application Studio的Dev Space Manger&#xff0c;选择创建Dev Space。 勾选HTML5 Application Template插件…...

设计模式--访问者模式

访问者模式是一种行为设计模式&#xff0c;它用于将算法与对象结构分离&#xff0c;使得算法可以独立于使用它的数据结构而变化。这种模式在许多应用场景中非常有用&#xff0c;例如在实现图形算法、数据结构遍历、文件格式转换以及代码分析时。 应用场景 图形算法&#xff1…...

onnx模型转换到rknn脚本

from rknn.api import RKNN ONNX_MODEL ./onnx_models/yolov5s_rm_transpose.onnx # platform"rk1808" platform "rv1109" RKNN_MODEL yolov5s_relu_{}_out_opt.rknn.format(platform) if __name__ __main__: add_perm False # 如果设置成True,则将模…...

防御恶意爬虫攻击

数据抓取爬虫 数据抓取爬虫是攻击者使用自动化脚本或工具在移动应用程序中抓取敏感数据的一种方式。这些爬虫可以定向抓取用户信息、产品列表、评论和评级等数据。攻击者可能会将这些数据用于非法目的&#xff0c;例如进行身份盗窃、诈骗活动或者卖给其他恶意方。 对于移动应用…...

【自动驾驶技术栈学习】2-软件《大话自动驾驶》| 综述要点总结 by.Akaxi

----------------------------------------------------------------------------------------------------------------- 致谢&#xff1a;感谢十一号线人老师的《大话自动驾驶》书籍&#xff0c;收获颇丰 链接&#xff1a;大话自动驾驶 (豆瓣) (douban.com) -------------…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...