回文链表
Palindrome Linked List
判断一条链表正着读和反着读是否完全相同。
在力扣中练习题目描述
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1] 输出：true
示例 2：
输入：head = [1,2] 输出：false
提示：
- 链表中节点数目在范围
[1, 105]内 0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
解题思路
快慢指针 + 反转后半段
找到中点，把后半段翻过来，再从两端往中间比
单链表不能从后往前走，最直接的办法是把值复制进数组，再用双指针比较；但那需要 O(n) 额外空间。想在 O(1) 空间内完成，就把后半段原地反转。
先用快慢指针找中点：fast 每次走两步，slow 走一步。fast 到尾时 slow 在中间；奇数长度会正好停在中点。
slow → node-1，fast → node-2。
然后从中点开始反转后半段，让右半段可以从前向后读。反转时每改一条 next，都要先保存原来的后继。
中点 node-3 已确定；从它开始把 next 反向，prev 先为 null。
prev→ null最后 left 从原头、right 从反转后的头同时前进，逐对比较，直到 right 走完。
left 回到 head，right 指向反转后的尾；现在比较两端。
自拟主例是奇数长度，两个指针最后会同时停在中点；这一次比较的是同一个节点，天然相等，不需要特殊跳过。
易错点
- 快指针初始化成 head->next：偶数长度会提前停在前半段末尾，后半段少一个节点。
- 反转循环写成 while (slow->next)：会漏掉最后一个节点，右半段缺尾。
- 比较循环用 while (left != right)：奇数长度会在中点卡住，必须用 right 是否走完来控制。
- 反转后没有恢复链表：如果调用方还要使用原链表，需要再反转一次还原。
复制到数组 · 双指针
先把链表拍平成数组，再判断回文
最好写、也最容易调试，但需要 O(n) 额外空间，不满足原地优化的目标。
遍历链表，把每个节点的值放进 vector，问题立刻变成“数组是否回文”。数组支持随机访问，左右指针相向而行即可。
这个方案不修改链表，也不会破坏调用方的数据；代价是 O(n) 额外空间。如果题目不限制空间，或者链表之后还要复用，它反而更安全。
面试里可以先说这个方案，再补上快慢指针版本，展示对空间复杂度的取舍。
- 1遍历链表，把值复制到数组。
- 2left、right 指向数组两端。
- 3相向比较，遇到不等返回 false。
- 4全部通过返回 true。
易错点
- 只比较值不比较位置：回文必须两端对称，不是集合相同。
- 空链表和单节点链表应直接返回 true。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
head = [2,9,4,7,4,9,2]slow、fast 从头出发；快指针每次走两步，慢指针走一步。
查看 C++ 代码
延伸阅读
- 快慢指针找中点 + 原地反转，是链表里反复出现的组合：回文、重排、折半都可以用。
- 如果要求判断后恢复原链表，记得在比较结束后再把后半段反转回去。