题目描述
判断单链表是否为回文(正读反读一样)。要求 O(1) 额外空间。
思路解析
把值全存进数组、再首尾双指针往中间比，简单，但要 O(n) 额外空间。想做到 O(1) 空间，得在链表本身上动手。
转折：这题其实是 876 找中点 和 206 反转链表 的合体。先快慢找中点，把后半段原地反转，再从原头和反转后的尾两头往中间走逐个比值——全相等就是回文，只花 O(1) 空间。
① 快慢找中点 · 起步：第一步找中点：slow 走 1 步、fast 走 2 步，都从头出发。下面分开移动看得清楚。
① slow→2, fast→第二个2：第 1 轮：slow 走 1 步到下标 1(值 2)，fast 走 2 步到下标 2(第二个 2)。fast 把 slow 甩开，领先正好是 slow 走过距离的两倍。
① slow→第二个2, fast 越界停：第 2 轮：slow 走到下标 2(第二个 2)，fast 想再跨两步就冲出链表(变 null)，循环条件 fast and fast.next 不成立、停。slow 此刻把链表分成前半 [1,2] 和后半 [2,1]，后半从 slow 开始。
② 反转后半段 · 起步：第二步反转后半段 [2,1]。后半只有下标 2、3 两个节点，要把它们之间那根箭头掉头。slow 当前指着后半的头(下标 2)。
② 后半段反转完成 [2,1]→[1,2]：用 206 的三指针把后半反转：下标 2、3 之间的箭头掉头(变 ←)，后半从 2→1 变成 1→2。反转后后半段的新头是最后那个 1(下标 3)，记作 prev。
③ 左右双指针 · 第一对：第三步比较：left 从原头(下标 0，值 1)、right 从反转后半的新头(下标 3，值 1)。比第一对：1 == 1 相等，两个一起往中间走。
③ 第二对 · left→2, right→2：left 沿正常箭头到下标 1(值 2)，right 沿反转后的箭头到下标 2(值 2)。比第二对：2 == 2 相等。right 再走就到 null，比较即将结束。
负例 · 若某对不等立即 false：反向想个负例：假如这一对不是 2 和 2，而是 2 ≠ 9，那一刻就能立即返回 false，不必比完——只要中途有一对不等，就不是回文。本例每对都相等，继续。
③ 全部相等 · 是回文：right 走到头(后半比完)，每一对都相等，返回 true。比较只走了半条链，不会越界。
难题往往是基础招式的拼装：找中点 + 反转 + 双指针。熟练的小套路，是解决大问题的积木——这正是「套路模板」的价值。
参考代码（Python）
1def isPalindrome(self, head):
2 slow = fast = head
3 while fast and fast.next: # ① 找中点
4 slow, fast = slow.next, fast.next.next
5 prev = None # ② 反转后半段
6 while slow:
7 slow.next, prev, slow = prev, slow, slow.next
8 left, right = head, prev # ③ 两头比较
9 while right: # 以后半 right 是否到头为准
10 if left.val != right.val: return False
11 left, right = left.next, right.next
12 return True复杂度分析
- 时间复杂度：O(n) —— 找中点、反转、比较都是线性扫一遍
- 空间复杂度：O(1) —— 只用几个指针原地反转，不开数组
套路模板
记住骨架：快慢找中点 → 从中点起反转 → prev 是后半新头。重排链表(143)、判回文都靠这套「中点+反转」组合拳。
1slow = fast = head
2while fast and fast.next: # 快慢找中点
3 slow, fast = slow.next, fast.next.next
4prev = None # 反转后半段
5while slow:
6 slow.next, prev, slow = prev, slow, slow.next
7# 现在 prev 是后半段反转后的头易错点
- 错误写法：比较时走完整条链(while left and right) → 正确写法：以后半 right 是否到头为准(while right)（奇数长度时前半比后半多一个，走完整条会越界或多比一次中间值）
- 错误写法：反转前忘了找中点、或顺序乱了 → 正确写法：严格按 找中点 → 反转后半 → 比较 三步（没先定位中点就反转，会把整条链或错误区段反掉，比的位置全错）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。