0234.回文链表
难度：🟢 简单
标签：链表、双指针、栈、递归
链接：234. 回文链表
题目描述
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
解题思路
核心思想
本题的核心是在一个只能单向遍历的链表中，判断其节点值序列是否中心对称。为了达到 O(1) 的空间复杂度，我们需要一种不依赖额外数组的巧妙方法。
思路选择
快慢指针 + 反转链表 是解决此问题的最优思路，可以将空间复杂度降至 O(1)。
找到前半部分的尾节点：使用快慢指针法，当快指针走完时，慢指针正好位于链表的中点。
反转后半部分链表：从慢指针的下一个节点开始，反转链表的后半部分。
比较前后两半：将链表的前半部分与反转后的后半部分进行逐一比较。如果所有对应节点的值都相等，则链表是回文的。
恢复链表（可选）：为了保持链表原始结构，可以再次反转后半部分链表，将其恢复原状。
关键步骤
找中点：初始化
slow和fast指针都指向head。fast每次走两步，slow每次走一步。当fast到达末尾时，slow就指向了前半部分的最后一个节点。反转后半段：从
slow.next开始，调用一个反转链表的函数，得到反转后后半段的头节点secondHalfStart。逐一比较：用两个指针，一个从
head开始，一个从secondHalfStart开始，同时向后遍历，比较节点值。一旦发现不相等，立即返回false。返回结果：如果比较顺利完成，说明链表是回文的，返回
true。
代码实现 (推荐)
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function(head) {
if (head === null || head.next === null) {
return true;
}
// 1. 找到链表中点
let slow = head, fast = head;
while (fast.next !== null && fast.next.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
// 2. 反转后半部分链表
const reverseList = (node) => {
let prev = null, curr = node;
while (curr !== null) {
let temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
};
let secondHalfStart = reverseList(slow.next);
// 3. 比较前后两半
let firstHalfPointer = head;
let secondHalfPointer = secondHalfStart;
let result = true;
while (result && secondHalfPointer !== null) {
if (firstHalfPointer.val !== secondHalfPointer.val) {
result = false;
}
firstHalfPointer = firstHalfPointer.next;
secondHalfPointer = secondHalfPointer.next;
}
// 4. (可选) 恢复链表
slow.next = reverseList(secondHalfStart);
return result;
};
原始代码分析 (用户提供)
您提供的解法思路也很独特，通过一次遍历完成了两件事：将链表值存入数组和原地反转链表，然后进行比较。
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function (head) {
var prev = null, cur = head, results = [];
// 第一次遍历：将链表值存入数组，同时原地反转链表
while (cur !== null) {
results.push(cur.val);
let temp = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
}
// 第二次遍历：比较反转后的链表和存储的原始值序列
// 此时 prev 是反转后链表的头节点
while (prev !== null) {
// 从数组头部取值，模拟原始链表的顺序
let val = results.shift();
if(prev.val !== val) return false;
prev = prev.next;
}
return true;
};
优点：想法新颖，将两个操作合并在一次循环中。
潜在优化点：此解法使用了 O(n) 的额外空间（
results数组），并且results.shift()操作本身的时间复杂度也是 O(n)，导致第二轮循环的整体时间复杂度为 O(n²)。推荐解法通过原地修改链表，将空间复杂度降到了 O(1)，是此类问题的最优解。
复杂度分析
时间复杂度：O(n) 其中 n 是链表的节点数。推荐解法中的找中点、反转、比较都只需要线性时间。
空间复杂度：O(1) 推荐解法只使用了常数个额外变量作为指针。
相关题目
总结
本题是链表操作的综合应用，它巧妙地将“快慢指针找中点”和“原地反转链表”这两个经典操作结合起来，以达到 O(1) 空间复杂度的要求。这是考察链表熟练程度的一道高质量面试题。