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

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

题目描述:
给你一个单链表的头节点 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),指针只占用了常量的空间。
相关文章:
回文链表(快慢指针解法之在推进过程中反转)
归纳编程学习的感悟, 记录奋斗路上的点滴, 希望能帮到一样刻苦的你! 如有不足欢迎指正! 共同学习交流! 🌎欢迎各位→点赞 👍 收藏⭐ 留言📝抱怨深处黑暗,不如提灯前行…...
深度剖析:为什么 Spring 和 IDEA 都不推荐使用 @Autowired 注解
目录 依赖注入简介 Autowired 注解的优缺点 Spring 和 IDEA 不推荐使用 Autowired 的原因 构造器注入的优势 Autowired 注解的局限性 可读性和可测试性的问题 推荐的替代方案 构造器注入 Setter 注入 Java Config Bean 注解 项目示例:Autowired vs 构造器…...
【接口自动化_05课_Pytest接口自动化简单封装与Logging应用】
一、关键字驱动--设计框架的常用的思路 封装的作用:在编程中,封装一个方法(函数)主要有以下几个作用:1. **代码重用**:通过封装重复使用的代码到一个方法中,你可以在多个地方调用这个方法而不是…...
信息学奥赛初赛天天练-14-阅读程序-字符数组、唯一分解定理应用
更多资源请关注纽扣编程微信公众号 1 2019 CSP-J 阅读程序1 (程序输入不超过数组或字符串定义的范围;判断题正确填√,错误填;除特殊说明外,判断题1.5分,选择题3分,共计40分) 1 输入的字符串只能由小写字母或大写字母组…...
K210 数字识别 笔记
一、烧写固件 连接k210开发板,点开烧录固件工具,选中固件,并下载 二、模型训练 网站:MaixHub 1、上传文件 2、开始标记数据 添加9个标签,命名为1~9,按键盘w开始标记,键盘D可以下一张图片&…...
人脸检测--FaceNet(四)
FaceNet 是一个由 Google 研究团队开发的人脸识别系统,它基于深度学习技术,可以实现高精度的人脸识别、验证和聚类任务。FaceNet 通过学习直接从图像像素到人脸嵌入的映射,使得它在各种人脸识别任务中表现出色。下面是对 FaceNet 的详细介绍&…...
Android性能优化方案
1.启动优化: application中不要做大量耗时操作,如果必须的话,建议异步做耗时操作2.布局优化:使用合理的控件选择,少嵌套。(合理使用include,merge,viewStub等使用)3.apk优化(资源文件优化&#…...
视频监控平台AS-V1000 的场景管理,一键查看多画面视频的场景配置、调用、管理(一键浏览多路视频)
目录 一、场景管理的定义 二、场景管理的功能和特点 1、功能 (1)场景配置 (2)实时监控 (3)权限管理 2、特点 三、AS-V1000的场景配置和调用 1、场景配置 (1)实时视频预览 …...
微服务架构五大设计模式详解,助你领跑行业
微服务架构设计模式详解(5种主流模式) 微服务架构 微服务,一种革命性的架构模式,主张将大型应用分解为若干小服务,通过轻量级通信机制互联。每个服务专注特定业务,具备独立部署能力,轻松融入生产环境,为系…...
【problem】解决EasyExcel导出日期数据显示为#####问题
前言 在使用EasyExcel进行数据导出时,你可能遇到日期或其他数据在Excel中显示为“#######”的情况,这通常是因为列宽不足以展示单元格内的全部内容。本文将指导你如何通过简单的步骤解决这一问题,并确保导出的Excel文件自动调整列宽或直接指…...
Pytest用例自定义 - 重复、并行、串行
简介:面对快速迭代和持续交付的需求,提高测试效率变得至关重要。并行测试因其显著的时间节省优势而备受青睐。然而,并非所有测试都适合并行执行。在某些情况下,串行执行是必要的,以确保测试的正确性和稳定性。本文将探…...
前端项目上线
目录 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种不同数据结构类型之间的映射如下: 结构类型结构存储的值结构的读写能力STRING可以是字符串、整数或者浮点数key-value形式;对整…...
Python pands使用引擎实现excel条件格式
截至我的知识更新日期(2023年),Pandas 库本身并不直接支持Excel条件格式。Pandas 是一个强大的Python数据分析库,它主要用于数据分析和操作,而不是用于创建或编辑Excel文件的格式。 然而,你可以使用 openp…...
基于 vuestic-ui 实战教程 - 登录篇
1. 简介 登录做为一个系统的门面,也是阻挡外界的一道防线,那在vuestic-ui中如何做登录功能呢。在这里就之间沿用初始版本的Login页面,作为一个演示模板,后续需要改进的读者可以在此篇文章的基础上修改。 2. 登录接口相关api 与 t…...
SAPUI5基础知识2 - 手动创建一个SAPUI5的项目
1. 前言 在本篇文章中,我们将手动一步一步建立出第一个SAPUI5的 ‘Hello World!’ 项目。 2. 步骤详解 2.1 在BAS中建立Dev Space 进入SAP Business Application Studio的Dev Space Manger,选择创建Dev Space。 勾选HTML5 Application Template插件…...
设计模式--访问者模式
访问者模式是一种行为设计模式,它用于将算法与对象结构分离,使得算法可以独立于使用它的数据结构而变化。这种模式在许多应用场景中非常有用,例如在实现图形算法、数据结构遍历、文件格式转换以及代码分析时。 应用场景 图形算法࿱…...
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,则将模…...
防御恶意爬虫攻击
数据抓取爬虫 数据抓取爬虫是攻击者使用自动化脚本或工具在移动应用程序中抓取敏感数据的一种方式。这些爬虫可以定向抓取用户信息、产品列表、评论和评级等数据。攻击者可能会将这些数据用于非法目的,例如进行身份盗窃、诈骗活动或者卖给其他恶意方。 对于移动应用…...
【自动驾驶技术栈学习】2-软件《大话自动驾驶》| 综述要点总结 by.Akaxi
----------------------------------------------------------------------------------------------------------------- 致谢:感谢十一号线人老师的《大话自动驾驶》书籍,收获颇丰 链接:大话自动驾驶 (豆瓣) (douban.com) -------------…...
以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
uniapp 字符包含的相关方法
在uniapp中,如果你想检查一个字符串是否包含另一个子字符串,你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的,但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...
C# 表达式和运算符(求值顺序)
求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如,已知表达式3*52,依照子表达式的求值顺序,有两种可能的结果,如图9-3所示。 如果乘法先执行,结果是17。如果5…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
Vue ③-生命周期 || 脚手架
生命周期 思考:什么时候可以发送初始化渲染请求?(越早越好) 什么时候可以开始操作dom?(至少dom得渲染出来) Vue生命周期: 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...
uniapp 实现腾讯云IM群文件上传下载功能
UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中,群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS,在uniapp中实现: 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...
vue3 daterange正则踩坑
<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...
