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.next），slow指针每步前进 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]为例（长度 n=4），内部各模块执行时的变量状态演进如下表所示：
| 阶段 / 步骤 | 当前控制变量状态 | 作用的目标物理区间 | 链表内部实时拓扑或状态值 | 动作与结论 |
|---|---|---|---|---|
| 中点定位阶段 | 初始：fast=head(1),slow=head(1) | 全局链表 | 1 -> 2 -> 2 -> 1 -> null | - |
| 中点定位步进 1 |
| 全局链表 | 1 -> 2 -> 2 -> 1 -> null | fast != null && fast.next != null成立，继续推进 |
| 中点定位步进 2 |
| 全局链表 | 1 -> 2 -> 2 -> 1 -> null | 循环终止，返回slow对应的子链表[2, 1] |
| 局部反转阶段 | 输入head2 = [2, 1]，执行反转 | 后半段链表区间 | 反转后结构变为：1 -> 2 -> null | 返回新头节点地址，指向数值为 1 的节点 |
| 比对第 1 步 |
| 两个子链表的首位 | 1 == 1成立 | 条件满足，head和head2同时后移一位 |
| 比对第 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)。