LeetCode 234. 回文链表
题目核心
给定一个单链表 head，判断它的节点值是否构成回文。
回文的意思是从前往后读和从后往前读完全一样。例如：
1 -> 2 -> 2 -> 1 是回文
1 -> 2 不是回文这道题的关键限制是：单链表只能向后遍历，不能直接从尾部向前走。
解题思考过程
第一步：理解问题
判断链表是否是回文，即正向和反向读一样。
第二步：暴力解法（数组）
最直接的思路：把链表的值复制到数组，然后用双指针判断是否回文。
时间复杂度：O(n)
空间复杂度：O(n)这个思路简单，但需要额外的数组空间。
第三步：思考如何优化空间
能不能不用额外空间？
想到：如果能把链表后半部分反转，然后和前半部分比较，就可以判断是否回文。
步骤：
1. 找到链表中点（快慢指针）
2. 反转后半部分链表
3. 比较前半部分和反转后的后半部分
4. 恢复链表（可选）第四步：找到链表中点
用快慢指针：
slow: 每次走一步
fast: 每次走两步
当 fast 到达末尾时，slow 就在中点位置。示例：1 -> 2 -> 2 -> 1
初始：slow=1, fast=1
第一次：slow=2, fast=2
第二次：slow=2, fast=null
slow 指向第二个2，这是后半部分的起点。第五步：反转后半部分
反转后的链表：1 -> 2 <- 2 <- 1
变成：
前半部分：1 -> 2
后半部分（反转后）：1 -> 2第六步：比较两部分
比较：1 == 1 ✓
比较：2 == 2 ✓
返回 true第七步：恢复链表（可选）
如果题目要求不修改原链表，需要把后半部分再反转回来。
第八步：方法对比
| 方法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 数组法 | O(n) | O(n) | 简单直观 |
| 反转后半部分 | O(n) | O(1) | 空间最优 |
反转后半部分是最优解法！
解法一：复制到数组后双指针
这是最直观的官方解法，也是当前 234.ts 的思路。
先遍历链表，把所有节点值存入数组。数组支持下标访问，所以可以用左右双指针判断是否回文。
function isPalindrome(head: ListNode | null): boolean {
const values: number[] = [];
while (head != null) {
values.push(head.val);
head = head.next;
}
let left = 0;
let right = values.length - 1;
while (left < right) {
if (values[left] !== values[right]) {
return false;
}
left++;
right--;
}
return true;
}算法思想
链表不能从尾部往前遍历，但数组可以随机访问。
所以这个方法先把链表问题转化成数组问题：
链表：1 -> 2 -> 2 -> 1
数组：[1, 2, 2, 1]然后比较：
values[0]和values[n - 1]values[1]和values[n - 2]- 直到两个指针相遇或交错
如果所有对应位置都相等，就是回文。
复杂度
- 时间复杂度：
O(n) - 空间复杂度：
O(n)
注意：这个方法需要额外数组，因此不是 O(1) 空间。
解法二：递归
递归解法利用调用栈走到链表尾部，再在递归返回时从后往前比较。
因为递归天然会先深入到最后一个节点，再逐层返回，所以它可以模拟“从尾部向前走”的效果。
function isPalindrome(head: ListNode | null): boolean {
let front: ListNode | null = head;
function check(current: ListNode | null): boolean {
if (current == null) {
return true;
}
if (!check(current.next)) {
return false;
}
if (front == null || front.val !== current.val) {
return false;
}
front = front.next;
return true;
}
return check(head);
}算法思想
递归函数 check(current) 会一路递归到链表末尾。
当递归开始回退时：
current按照尾节点、倒数第二个节点、倒数第三个节点的顺序出现。- 外层变量
front从头节点开始向后走。 - 每次比较
front.val和current.val。
也就是说，递归返回阶段让我们同时拿到了：
front 从前往后走
current 从后往前回退如果所有对应节点值都相等，就是回文。
复杂度
- 时间复杂度：
O(n) - 空间复杂度：
O(n)
空间复杂度来自递归调用栈。虽然没有显式创建数组，但递归栈仍然会占用和链表长度相关的空间。
解法三：反转后半段链表
这是官方推荐的进阶解法，满足 O(n) 时间和 O(1) 额外空间。
核心步骤：
- 用快慢指针找到前半段的尾节点。
- 反转后半段链表。
- 从头节点和反转后的后半段头节点开始逐个比较。
- 比较结束后，可以把后半段再反转回来，恢复原链表结构。
function isPalindrome(head: ListNode | null): boolean {
if (head == null) {
return true;
}
const firstHalfEnd = endOfFirstHalf(head);
const secondHalfStart = reverseList(firstHalfEnd.next);
let p1: ListNode | null = head;
let p2: ListNode | null = secondHalfStart;
let result = true;
while (result && p2 != null) {
if (p1 == null || p1.val !== p2.val) {
result = false;
}
p1 = p1.next;
p2 = p2.next;
}
firstHalfEnd.next = reverseList(secondHalfStart);
return result;
}
function endOfFirstHalf(head: ListNode): ListNode {
let slow: ListNode = head;
let fast: ListNode | null = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next!;
fast = fast.next.next;
}
return slow;
}
function reverseList(head: ListNode | null): ListNode | null {
let prev: ListNode | null = null;
let current: ListNode | null = head;
while (current != null) {
const next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}快慢指针如何找前半段结尾
slow 每次走一步，fast 每次走两步。
当 fast 走到链表末尾时，slow 正好停在前半段的最后一个节点。
例如偶数长度：
1 -> 2 -> 2 -> 1
^
slow 停在第一个 2例如奇数长度：
1 -> 2 -> 3 -> 2 -> 1
^
slow 停在 3反转从 slow.next 开始的后半段，这样奇数长度时中间节点不会参与比较。
为什么只比较后半段长度
后半段反转后：
原链表： 1 -> 2 -> 2 -> 1
反转后半段： 1 -> 2此时从 head 和 secondHalfStart 同时向后走。
只要后半段走完都匹配，前半段对应位置也就都匹配。奇数长度时，中间节点本来就不影响回文判断。
三种解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 数组 + 双指针 | O(n) | O(n) | 最直观，代码简单 |
| 递归 | O(n) | O(n) | 利用递归回退模拟反向遍历 |
| 反转后半段 | O(n) | O(1) | 最优空间，需要处理链表指针 |
面试中如果题目要求进阶到 O(1) 空间，应使用反转后半段链表的方法。