力扣hot100-234.回文链表-快慢指针与反转详解

234. 回文链表：快慢指针与反转详解

题目链接：234. 回文链表

算法思路

链表 / 快慢指针 / 反转后半段 / 双指针比较

回文的含义是：从左往右读，与从右往左读完全一样。

例如：

1 -> 2 -> 2 -> 1

从两端向中间看：

第 1 个节点和倒数第 1 个节点：1 == 1 第 2 个节点和倒数第 2 个节点：2 == 2

因此它是回文链表。

本题的核心流程是：

找中点 -> 奇数长度时跳过中点 -> 反转后半段 -> 从两端向中间比较

1. 为什么链表需要先反转后半段

如果是数组，可以直接通过下标从两端读取：

nums[left]nums[right]

但单链表只能沿着next从前往后走：

1 -> 2 -> 2 -> 1

虽然可以从第一个节点走到最后一个节点，却不能从最后一个节点走回前一个节点。

也就是说，链表没有办法像数组一样直接比较：

第一个节点 与 最后一个节点 第二个节点 与 倒数第二个节点

解决方式是把后半段反转。

例如：

原链表：1 -> 2 -> 2 -> 1 后半段：2 -> 1 反转后：1 -> 2

现在可以同时从前向后读取两段：

左半段：1 -> 2 右半段：1 -> 2

原本的“从两端比较”，就转换成了“两个指针从前向后比较”。

2. 如何找到中点：快慢指针

定义两个指针：

ListNodeslow=head;ListNodefast=head;

移动规则：

slow 每轮走 1 步 fast 每轮走 2 步

因此：

fast 到达末尾时，slow 正好到达链表中间。

代码：

while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;}

循环条件中的两个判断含义分别是：

fast != null：fast 当前仍在链表内。 fast.next != null：fast 还能再走两步，不会访问空指针。

3. 偶数长度时，slow在哪里

假设链表为：

1 -> 2 -> 2 -> 1

初始：

1 -> 2 -> 2 -> 1 ^ slow、fast

第 1 轮后：

1 -> 2 -> 2 -> 1 ^ ^ slow fast

第 2 轮后：

1 -> 2 -> 2 -> 1 ^ slow fast = null

此时slow指向后半段的第一个节点：

1 -> 2 | 2 -> 1 ^ slow

所以偶数长度时，直接从slow开始反转后半段即可。

4. 奇数长度时，为什么要跳过中点

假设链表为：

1 -> 2 -> 3 -> 2 -> 1

快慢指针结束时：

1 -> 2 -> 3 -> 2 -> 1 ^ ^ slow fast

此时：

slow 指向正中间节点 3 fast 不为 null，且停在最后一个节点 1

中间节点3没有需要比较的配对节点：

1 <-> 1 2 <-> 2 3 不需要配对

因此应跳过它：

if(fast!=null){slow=slow.next;}

跳过后：

1 -> 2 -> 3 | 2 -> 1 ^ slow

之后只反转2 -> 1，让它与左半段1 -> 2对齐比较。

为什么用fast != null判断奇数长度？

偶数长度：fast 每次刚好跨过两个节点，最终走到 null。 奇数长度：最后会剩一个节点无法再走两步，fast 停在最后一个节点，不是 null。

5. 完整推演：1 -> 2 -> 3 -> 2 -> 1

第一步：找到中点并跳过它

快慢指针结束时：

1 -> 2 -> 3 -> 2 -> 1 ^ slow

因为fast != null，这是奇数长度，跳过中间节点3：

1 -> 2 -> 3 -> 2 -> 1 ^ slow

第二步：反转后半段

从slow开始的后半段是：

2 -> 1 -> null

反转后，得到：

1 -> 2 -> null

它代表原链表从右到左读到的节点值。

第三步：逐个比较

此时：

left： 1 -> 2 -> 3 -> ... right： 1 -> 2 -> null

比较过程：

left 的 1 == right 的 1，继续。 left 的 2 == right 的 2，继续。 right 到达 null，比较完成。

所以该链表是回文链表。

6. Java 代码完整注释

classSolution{publicbooleanisPalindrome(ListNodehead){// 空链表或只有一个节点时，从正反两个方向读都相同。if(head==null||head.next==null){returntrue;}// slow 每轮走一步，fast 每轮走两步。// fast 到末尾时，slow 会到达链表中间位置。ListNodeslow=head;ListNodefast=head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;}// fast 不为 null，说明节点数为奇数。// slow 此时指向正中间节点；中点无需比较，直接跳过。if(fast!=null){slow=slow.next;}// 反转后半段。// right 的遍历顺序等价于从原链表尾部向中间读取。ListNoderight=reverse(slow);// left 从原链表头部开始读取。ListNodeleft=head;// 后半段长度不会超过前半段。// 右半段全部匹配，就说明整条链表是回文。while(right!=null){if(left.val!=right.val){returnfalse;}left=left.next;right=right.next;}returntrue;}privateListNodereverse(ListNodehead){// pre 指向已经反转完成部分的头节点。ListNodepre=null;// cur 指向当前需要反转的节点。ListNodecur=head;while(cur!=null){// 保存原来的下一个节点。// 因为下一步会覆盖 cur.next，必须先保住后续链表。ListNodenext=cur.next;// 让当前节点指向前一个节点，完成当前节点的反转。cur.next=pre;// 移动指针，继续反转原链表中的下一个节点。pre=cur;cur=next;}// pre 指向反转后链表的新头节点。returnpre;}}

7. 为什么只比较到right == null

right是反转后的后半段。

对于偶数长度：

左半段长度 == 右半段长度

对于奇数长度，跳过中点后：

左侧可比较节点数 == 右半段长度

所以无论奇偶，只要右半段的每个节点都与左侧对应节点相同，就已经完成了所有必要比较：

while(right!=null)

不需要等待left走到null；奇数长度时，left还会多经过中间节点以及后半段，而它们都不应该重复参与比较。

8. 这段代码会改变原链表吗

会，且改变发生在这一步：

ListNoderight=reverse(slow);

它会把原链表的后半段原地反转。

LeetCode 这题通常只要求返回是否回文，允许这种做法，因为题目不会在方法返回后继续检查原链表的结构。

如果在实际业务代码中，后续还要使用原链表的原始顺序，应当在比较结束后：

再次反转 right，把后半段恢复。

这不会改变时间复杂度，仍然是O(n)。

9. 复杂度

假设链表有n个节点。

时间复杂度：

找中点：O(n) 反转后半段：O(n) 比较两半：O(n) 总计：O(n)

虽然进行了多个阶段，但它们都是对链表进行常数次遍历，因此总时间复杂度仍是线性的。

额外空间复杂度：

O(1)

只使用了有限个指针变量，没有使用数组、栈或HashSet。

一句话记忆：

快慢指针找中点；奇数长度跳过中点；反转后半段；用左右指针从前向后逐个比较。