力扣（回文链表）-北京尧图网络

解析 LeetCode 234. 回文链表快慢指针后半段反转一、题目分析一问题定义给定一个单链表的头节点 head判断该链表是否为回文链表。例如 head [1,2,2,1] 返回 true。head [1,2] 返回 false。链表节点数范围是 1 到 10^5值为整数要求空间复杂度 O(1)。二核心挑战效率要求必须 O(n) 时间 O(1) 额外空间排除转数组、递归栈、哈希表等方案。结构适配单链表无法倒序遍历需通过反转局部子链实现双向比对但反转会破坏原结构必须精准控制断链与恢复时机。二、算法思路快慢指针找中点反转后半段一奇偶长度下慢指针终止位置差异奇数长度如 5 个节点慢指针停在正中节点第 3 个后半段从 next 开始即第 4 个。偶数长度如 4 个节点慢指针停在前半段末尾第 2 个后半段从 next 开始即第 3 个。统一处理快指针走完时慢指针刚好落在后半段起始位置的前一个所以后半段头 slow.next。二反转后半段时断链与恢复的时机断链时机找到后半段头后立即将 slow.next 置为 null切断前后两段避免比对时误连。恢复时机比对完成后将已反转的后半段再次反转再接回 slow.next还原原始链表结构。关键细节反转操作本身不依赖原链表后续断链后可安全反转。恢复只需对反转后的子链再做一次反转即可。三、代码实现与详细解析publicclassSolution{publicbooleanisPalindrome(ListNodehead){if(headnull||head.nextnull){returntrue;}// 快慢指针初始化slow 和 fast 都从 head 出发ListNodeslowhead;ListNodefasthead;// 移动快慢指针fast 走两步slow 走一步直到 fast 到达末尾// 奇数长度时 fast 停在 tail偶数时停在 tail.nextnullwhile(fast.next!nullfast.next.next!null){slowslow.next;fastfast.next.next;}// 此时 slow 停在前半段末尾后半段头是 slow.nextListNodesecondHalfHeadslow.next;// 断链切断前半段和后半段的连接避免比对干扰slow.nextnull;// 反转后半段链表得到新头节点 reversedSecondHalfListNodereversedSecondHalfreverseList(secondHalfHead);// 初始化两个指针分别从前半段头和反转后的后半段头开始比对ListNodep1head;ListNodep2reversedSecondHalf;booleanisPalintrue;// 逐节点比对p1 和 p2 同时前进值不同则不是回文while(p1!nullp2!null){if(p1.val!p2.val){isPalinfalse;break;}p1p1.next;p2p2.next;}// 恢复链表将已反转的后半段再次反转接回 slow.nextslow.nextreverseList(reversedSecondHalf);returnisPalin;}// 辅助函数反转链表返回新头节点privateListNodereverseList(ListNodehead){ListNodeprevnull;ListNodecurrhead;// 遍历原链表逐个将 curr 指向 prev实现反转while(curr!null){ListNodenextTempcurr.next;// 保存下一个节点防止断链丢失curr.nextprev;// 当前节点指向前面节点prevcurr;// prev 前移一位currnextTemp;// curr 前移一位}returnprev;// prev 是新头节点}}一代码流程拆解初始化处理空链表或单节点情况直接返回 true。设置 slow 和 fast 均指向 head。快慢指针移动 fast 每次走两步slow 每次走一步循环条件是 fast.next 和 fast.next.next 都非空确保 fast 不越界。定位后半段头循环结束时 slow 停在前半段末尾secondHalfHead slow.next 即为后半段起点。断链操作将 slow.next 置 null彻底分离前后两段。反转后半段调用 reverseList 得到反转后的后半段头节点。双指针比对 p1 从前半段头出发p2 从反转后半段头出发同步前进比对值任一不等即返回 false。恢复链表对已反转的后半段再调用 reverseList结果接回 slow.next还原原始结构。返回结果比对全程相等则返回 true否则 false。二关键逻辑解析断链时机快慢指针停稳后立刻执行 slow.next null否则比对时 p2 可能顺着原链表继续走到前半段造成错误匹配。例如 [1,2,3,2,1] 中若不断链p2 从 3 开始反转后为 [1,2,3]但未断链时仍连着 2→1比对会混乱。恢复必要性题目虽未要求保持原链表但实际工程中修改输入结构需谨慎且部分 OJ 测试用例会复用链表恢复可避免副作用。奇偶统一性无论长度奇偶slow 停点都是后半段起始的前一个所以 secondHalfHead slow.next 恒成立无需分支判断。四、复杂度分析一时间复杂度O(n)其中 n 是链表长度。快慢指针遍历约 n/2 次反转后半段约 n/2 次比对最多 n/2 次恢复反转又 n/2 次总和为 O(n)。二空间复杂度O(1)只使用了 slow、fast、p1、p2、prev、curr 等常数个指针变量无递归栈、无额外容器。

力扣（回文链表）

相关推荐

瑞昱发布 Wi-Fi R-NAT 解决方案：在 RTOS SoC 原生实现三层路由与独立组网

Claude Code 的国产平替？AtomCode 功能解读与新手入门教程

上海实力型EMBA选校避坑FAQ、核心判断维度全解析，附上海交大高金教育背景梳理

更多资讯

二维瓦片的相关概念

CAN 技术系列 07 · CAN 高层协议

线规对了为什么还压不好？端子压接范围、绝缘外径与拉脱力匹配

CAN 技术系列 06 · CAN 错误处理与错误帧

导师退回问题清单：论文从开题到定稿，AI 工具到底该怎么选、怎么用

OpenStack 计算管理：实例锁定后被普通用户解锁了？避坑实操

今日更新

猫狗目标检测数据集：VOC/COCO/YOLO三格式一体化实战包

HDU2017多校标程复现：算法竞赛工程化真题沙盒

Codex Sandbox 隔离环境拆解：AI Agent 的临时实验室如何运作

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？