)
本算法采用快慢指针定位、局部链表反转与双指针线性比对的组合方案解决“回文链表”判定问题。其核心本质是在不开辟额外存储空间的前提下通过修改原链表后半段的拓扑结构实现前后数据的空间对齐。当前提供的源码实现了时间复杂度 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)。
)
