力扣（回文链表）

解析 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 等常数个指针变量无递归栈、无额外容器。