hot100 回文链表(234)
本算法采用快慢指针定位、局部链表反转与双指针线性比对的组合方案解决“回文链表”判定问题。其核心本质是在不开辟额外存储空间的前提下通过修改原链表后半段的拓扑结构实现前后数据的空间对齐。当前提供的源码实现了时间复杂度 O(n) 和额外空间复杂度 O(1) 的最优资源配置方案最终走向是通过同步比对两个子链表的节点数值输出布尔判定结果。一、 问题本质与数学模型对于长度为 n 的单链表若其满足回文特性则链表从前向后遍历的节点数值序列与从后向前遍历的节点数值序列完全一致。链表的物理结构只支持单向单驱寻址next指针无法直接进行双向逆序比对。为了在常数阶空间内完成判定必须将链表在逻辑上切分为两个子链表前半段链表从原始头节点head开始包含前 ⌊n/2⌋ 个节点。后半段链表从中间节点开始直到尾节点并将其拓扑结构完全反转形成以反转后的尾节点为新头节点head2的逆序子链表。比对两段子链表的数值序列若在head2遍历至null期间所有对应节点的val全部相等则该链表在数学上确立为回文链表。二、 算法演进对比在解决单链表回文验证问题时各解法的资源消耗特征如下解法名称时间复杂度空间复杂度核心原理物理缺陷 / 瓶颈辅助数组/列表法O(n)O(n)将链表所有节点数值复制到动态数组中利用双指针向中间靠拢比对数值引入了与链表节点总数成正比的额外内存开销非原地算法链表完全克隆反转O(n)O(n)复制一份完全相同的链表并将其整体反转随后同步比对原链表与新链表需要完整的二次节点内存分配栈结构逆序比对O(n)O(n)将链表全量节点压入栈中随后出栈与原链表节点进行比对栈帧或数据存储引发线性空间损耗快慢指针局部反转当前解法O(n)O(1)用快慢指针锁定中点原地反转后半段链表并进行线性比对改变了原链表的后半段物理结构若需恢复原状需二次反转三、 核心控制逻辑拆解该算法由三个独立的、互不嵌套的模块组合而成1. 快慢指针定位中点mid函数变量职责fast指针每步前进 2 个节点fast.next.nextslow指针每步前进 1 个节点slow.next。运行机制当fast触及链表末尾null或尾节点时slow指针恰好停留在链表的几何中点位置对于奇数长度停留在正中节点对于偶数长度停留在后半段的首个节点。该函数返回slow处的节点地址作为后半段链表的起点。2. 原地链表反转reverse函数运行机制利用cur,pre,nxt三个局部指针单次线性扫描后半段链表逐位逆转next指针的指向最后返回逆序链表的新头节点地址pre。3. 同步双指针比对isPalindrome主逻辑控制条件while (head2 ! null)。因为后半段链表的长度必然小于或等于前半段链表的长度所以以head2释放作为判定终止信号。判定机制每轮循环检测head2.val ! head.val。若成立则直接终止流程并返回false若相等则两个指针同时后移。四、 算法执行状态机步进示例以输入数据head [1, 2, 2, 1]为例长度 n4内部各模块执行时的变量状态演进如下表所示阶段 / 步骤当前控制变量状态作用的目标物理区间链表内部实时拓扑或状态值动作与结论中点定位阶段初始fasthead(1),slowhead(1)全局链表1 - 2 - 2 - 1 - null-中点定位步进 1fast推进至第三个节点2slow推进至第二个节点2全局链表1 - 2 - 2 - 1 - nullfast ! null fast.next ! null成立继续推进中点定位步进 2fast推进至nullslow推进至第三个节点2全局链表1 - 2 - 2 - 1 - null循环终止返回slow对应的子链表[2, 1]局部反转阶段输入head2 [2, 1]执行反转后半段链表区间反转后结构变为1 - 2 - null返回新头节点地址指向数值为 1 的节点比对第 1 步head指向第一个节点1head2指向反转后新头节点1两个子链表的首位1 1成立条件满足head和head2同时后移一位比对第 2 步head指向第二个节点2head2指向反转后第二个节点2两个子链表的第二位2 2成立条件满足head和head2同时后移一位终止判定head2变为null比对结束-while循环破裂未触发不相等分支最终输出true五、源码实现/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public boolean isPalindrome(ListNode head) { // 步骤 1定位链表的后半段起点 ListNode head2 mid(head); // 步骤 2原地反转后半段链表 head2 reverse(head2); // 步骤 3同步比对前半段与反转后的后半段 // 以较短的后半段链表完全释放为循环终止标准 while (head2 ! null) { if (head2.val ! head.val) { return false; // 数值不匹配判定非回文 } head2 head2.next; head head.next; } return true; } /** * 利用快慢指针寻找链表中点的辅助方法 */ private ListNode mid(ListNode head) { ListNode fast head; ListNode slow head; // 快指针每步走2格慢指针每步走1格 while (fast ! null fast.next ! null) { fast fast.next.next; slow slow.next; } return slow; } /** * 原地反转单链表的辅助方法 */ private ListNode reverse(ListNode head) { ListNode cur head; ListNode pre null; while (cur ! null) { ListNode nxt cur.next; // 暂存后继节点 cur.next pre; // 逆转指针指向 pre cur; // 前驱指针推进 cur nxt; // 当前指针推进 } return pre; // 返回逆序后的新头节点 } }六、 复杂度极限分析1. 时间复杂度O(n)精确摊还分析定位中点模块快指针每次步进 2遍历完成时慢指针移动了 ⌊n/2⌋ 步。反转局部链表模块仅对后半段长度为 ⌈n/2⌉ 的子链表进行单次遍历耗时 ⌈n/2⌉ 步。同步线性比对模块最多执行 ⌈n/2⌉ 次比对。结论算法总体基本指令的执行总次数不超过 1.5n 次时间开销与链表总长度 n 呈严格的线性正比关系。2. 空间复杂度O(1)分析该算法的所有改写、翻转和比对逻辑均直接施加在传入的原始链表物理节点内存块上。执行期间算法仅在栈内存中开辟了head2、fast、slow、cur、pre、nxt等有限个引用类型的局部控制变量。结论没有申请任何与输入规模相关的外部数据结构其分配的额外物理内存空间始终保持固定空间复杂度为常数阶 O(1)。

相关新闻

遗传算法工程实战:选择、交叉、变异与终止的四大核心调优

遗传算法工程实战:选择、交叉、变异与终止的四大核心调优

1. 这不是教科书里的遗传算法,而是我调试了73次后才敢写的实操指南“遗传算法”这四个字,听上去像生物课上讲DNA双螺旋时顺带提的一句术语,又像AI面试题里那个永远答不全的“请手推GA流程”。但真实情况是:我在工业缺陷检测项目里…

2026/7/4 22:56:02阅读更多 →
STM32L021K4与LV30条码扫描器的低功耗嵌入式方案

STM32L021K4与LV30条码扫描器的低功耗嵌入式方案

1. 项目概述:LV30条码扫描器与STM32L021K4的硬件协同方案 在工业自动化、物流管理和零售结算等领域,条码识别系统的可靠性和适应性直接影响着整体效率。LV30作为一款高性能线性条码扫描器,配合STM32L021K4超低功耗微控制器的组合,…

2026/7/4 22:56:02阅读更多 →
智能工具如何提升MBA论文写作效率与质量

智能工具如何提升MBA论文写作效率与质量

1. 学术写作的智能化转型去年帮导师审阅MBA论文时,发现超过60%的参考文献都来自几个特定的智能学术平台。这让我意识到,当代学术研究方式正在经历一场静默革命——过去需要泡图书馆数周才能完成的文献工作,现在通过智能工具组合能在72小时内达…

2026/7/4 22:56:02阅读更多 →
不会写 Testbench 时,先用动态电路图看懂 Verilog

不会写 Testbench 时,先用动态电路图看懂 Verilog

不会写 Testbench 时,先用动态电路图看懂 Verilog很多同学刚开始学 Verilog 或 VHDL 时,最怕的不是语法本身,而是代码跑起来以后不知道该看哪里。一个 assign、一个 always 块,看书时似乎都能理解;可一到课程实验&…

2026/7/4 23:56:07阅读更多 →
D类音频功放MAX9744与TM4C1299的高效设计方案

D类音频功放MAX9744与TM4C1299的高效设计方案

1. 项目背景与核心价值在音频系统设计中,功率放大环节往往决定着最终输出的音质表现和能效水平。传统AB类放大器虽然线性度良好,但普遍存在效率低下(通常仅30%-50%)、发热严重的问题。而D类放大器通过PWM调制技术,可将…

2026/7/4 23:56:07阅读更多 →
Java毕业设计-基于 SpringBoot 的家校互联管理系统的设计与实现 智慧校园家校互动信息管理系统(源码+LW+部署文档+全bao+远程调试+代码讲解等)

Java毕业设计-基于 SpringBoot 的家校互联管理系统的设计与实现 智慧校园家校互动信息管理系统(源码+LW+部署文档+全bao+远程调试+代码讲解等)

博主介绍:✌️码农一枚 ,专注于大学生项目实战开发、讲解和毕业🚢文撰写修改等。全栈领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java、小程序技术领域和毕业项目实战 ✌️技术范围:&am…

2026/7/4 23:56:07阅读更多 →
MC6470与PIC18F25K80在工业控制中的高精度定位方案

MC6470与PIC18F25K80在工业控制中的高精度定位方案

1. 项目概述:MC6470与PIC18F25K80的强强联合在工业控制和精确定位领域,MC6470六轴惯性测量单元(IMU)与PIC18F25K80微控制器的组合堪称黄金搭档。这套方案能实现0.1的姿态测量精度和毫米级的位移定位,特别适合无人机飞控、工业机器人导航等需要…

2026/7/4 23:56:07阅读更多 →
抖音下载器完整指南:5分钟学会免费批量下载抖音视频

抖音下载器完整指南:5分钟学会免费批量下载抖音视频

抖音下载器完整指南:5分钟学会免费批量下载抖音视频 【免费下载链接】douyin-downloader A practical Douyin downloader for both single-item and profile batch downloads, with progress display, retries, SQLite deduplication, and browser fallback support…

2026/7/4 23:56:07阅读更多 →
ngx_http_test_expect

ngx_http_test_expect

1 定义 ngx_http_test_expect 函数 定义在 ./nginx-1.24.0/src/http/ngx_http_request_body.c2 目的 HTTP 协议中的 Expect 头部 HTTP 请求由“请求头部”和可选的“请求体”组成。 请求头部里可以包含一个字段叫 Expect。Expect 字段的作用是: 客户端在真正发送请求…

2026/7/4 23:51:06阅读更多 →
AI Coding 六个月真实ROI账本:产品经理的血泪教训,研发的冷静忠告

AI Coding 六个月真实ROI账本:产品经理的血泪教训,研发的冷静忠告

6个月前的2025年12月,Boris Cherny 公开宣布自己卸载了 IDE。一时间,Vibe Coding 成了全行业最热的话题。6个月后,当我们回过头来拉一份真实账本,发现事情远没有"一句话生成一个App"那么浪漫。本文从产品经理和研发两个…

2026/7/4 14:25:39阅读更多 →
审计来了,数据权限全开——审计走了,怎么确保权限全部关掉?

审计来了,数据权限全开——审计走了,怎么确保权限全部关掉?

引言:审计结束三个月了,审计员的权限还没关某城商行每年按照监管要求开展至少一次数据安全审计。审计期间,内审部门需要抽样检查各类业务数据——交易流水、客户信息、员工操作日志、权限配置记录。这些数据分布在不同系统中,审计…

2026/7/4 14:57:00阅读更多 →
端到端自动驾驶:从GTC‘26看工程可信落地的核心逻辑

端到端自动驾驶:从GTC‘26看工程可信落地的核心逻辑

1. 项目概述:当算法工程师走进GTC26展厅,看到的不是芯片,而是“端到端”的呼吸节奏“端到端”这三个字,在GTC’26现场出现的频率,高得像NVLink带宽测试时的峰值曲线——它不再是一个论文里的技术路径选项,而…

2026/7/4 0:02:48阅读更多 →
缺牙修复科普:常见义齿类型与选择参考

缺牙修复科普:常见义齿类型与选择参考

缺牙修复科普:常见义齿类型与选择参考牙齿缺失是中老年人群中较为常见的口腔问题,不仅会造成咀嚼不便、进食受影响,长期还可能对营养摄入与日常社交带来困扰。义齿是改善缺牙问题的常用方式,目前市面上的义齿种类较多,…

2026/7/4 0:02:48阅读更多 →
STM32F091RC与LTC6904实现高精度方波信号生成

STM32F091RC与LTC6904实现高精度方波信号生成

1. 项目概述:LTC6904与STM32F091RC的精准方波生成方案在嵌入式系统开发中,精确的时钟信号和定时控制往往是项目成败的关键。LTC6904作为一款低功耗、高精度的可编程振荡器芯片,与STM32F091RC这款ARM Cortex-M0内核微控制器的组合,…

2026/7/4 0:02:48阅读更多 →
YOLOv8推理性能优化:从1.2FPS到35FPS的全链路加速实践

YOLOv8推理性能优化:从1.2FPS到35FPS的全链路加速实践

如果你在部署 YOLOv8 时,发现推理速度只有可怜的 1-2 FPS,而别人的演示视频却能跑到 30 FPS 以上,那么问题很可能不在模型本身,而在于你的整个处理链路。很多开发者拿到一个训练好的 YOLOv8 模型后,会直接使用官方示例…

2026/7/4 1:16:56阅读更多 →
Coze与Dify对比指南:低代码AI应用开发从入门到实战

Coze与Dify对比指南:低代码AI应用开发从入门到实战

1. 从零到一:为什么你需要了解 Coze 和 Dify?如果你对 AI 应用开发感兴趣,但一看到“大模型”、“智能体”、“工作流”这些词就头疼,觉得门槛太高,那这篇文章就是为你准备的。很多开发者,包括我自己&#…

2026/7/4 2:33:55阅读更多 →
AI生图工具怎么选?2026年6月版实测对比

AI生图工具怎么选?2026年6月版实测对比

做自媒体的朋友应该都有体会:配图一直是个让人头疼的问题。2026年,AI生图工具已经非常成熟了,但工具太多反而不知道怎么选。以下是截至2026年6月我对主流AI生图工具的实测对比。Midjourney V8.1:速度之王2026年6月11日&#xff0c…

2026/7/4 2:33:55阅读更多 →