234. 回文链表
题目描述
输入一个单链表的头节点 head，链表用数组形式表示，例如 [1,2,2,1]。
判断这个链表是否为回文：从头往尾读和从尾往头读，得到的值序列完全一样。是回文返回 true，否则返回 false。
示例 1
输入：head = [1,2,2,1] 输出：true
解释：正读和倒读都是 1,2,2,1。
示例 2
输入：head = [1,2] 输出：false
解释：正读是 1,2，倒读是 2,1，二者不同。
数据范围
- 节点个数在
[1, 10^5]之间。 0 <= Node.val <= 9
进阶：能否做到 O(n) 时间、O(1) 额外空间？
解题思路：快慢指针 + 反转后半段
快慢指针找到后半段起点，反转后半段，再同步比较前半段和反转后的后半段。
为什么正确
比较阶段，左指针和右指针分别代表原序列的相对两端，已比较部分全部相等。
复杂度分析
时间 O(n)，额外空间 O(1)。
易错点
快慢指针的中点边界要覆盖奇数和偶数长度，比较时只需遍历反转后的后半段。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def isPalindrome(self, head):
slow=fast=head
while fast and fast.next: slow=slow.next; fast=fast.next.next
prev=None
while slow:
nxt=slow.next; slow.next=prev; prev=slow; slow=nxt
left,right=head,prev
while right:
if left.val!=right.val: return False
left,right=left.next,right.next
return Trueclass Solution {
public boolean isPalindrome(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
ListNode prev = null;
while (slow != null) {
ListNode nxt = slow.next; slow.next = prev; prev = slow; slow = nxt;
}
ListNode left = head, right = prev;
while (right != null) {
if (left.val != right.val) return false;
left = left.next; right = right.next;
}
return true;
}
}class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
ListNode* prev = nullptr;
while (slow) {
ListNode* nxt = slow->next; slow->next = prev; prev = slow; slow = nxt;
}
ListNode *left = head, *right = prev;
while (right) {
if (left->val != right->val) return false;
left = left->next; right = right->next;
}
return true;
}
};func isPalindrome(head *ListNode) bool {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow, fast = slow.Next, fast.Next.Next
}
var prev *ListNode
for slow != nil {
nxt := slow.Next; slow.Next = prev; prev = slow; slow = nxt
}
left, right := head, prev
for right != nil {
if left.Val != right.Val {
return false
}
left, right = left.Next, right.Next
}
return true
}var isPalindrome = function(head) {
let slow = head, fast = head;
while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
let prev = null;
while (slow) {
const nxt = slow.next; slow.next = prev; prev = slow; slow = nxt;
}
let left = head, right = prev;
while (right) {
if (left.val !== right.val) return false;
left = left.next; right = right.next;
}
return true;
};function isPalindrome(head: ListNode | null): boolean {
let slow = head, fast = head;
while (fast && fast.next) { slow = slow!.next; fast = fast.next.next; }
let prev: ListNode | null = null;
while (slow) {
const nxt: ListNode | null = slow.next; slow.next = prev; prev = slow; slow = nxt;
}
let left = head, right = prev;
while (right) {
if (left!.val !== right.val) return false;
left = left!.next; right = right.next;
}
return true;
};其他解法
复制到数组用 O(n) 空间换来随机访问，写法简单；快慢指针 + 反转后半段只用 O(1) 空间，但会修改链表结构。
解法 2：复制到数组 + 双指针 时间 O(n)，空间 O(n)
遍历链表，把节点值依次存入数组。左指针从头、右指针从尾向中间移动，遇到不相等就返回 false。两指针相遇仍未返回就是回文。
写法最简单，不修改链表。需要 O(n) 额外空间，不满足进阶要求。
class Solution:
def isPalindrome(self, head):
vals = []
while head:
vals.append(head.val)
head = head.next
i, j = 0, len(vals) - 1
while i < j:
if vals[i] != vals[j]:
return False
i += 1
j -= 1
return Trueclass Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> vals = new ArrayList<>();
for (ListNode p = head; p != null; p = p.next) vals.add(p.val);
int i = 0, j = vals.size() - 1;
while (i < j) {
if (!vals.get(i).equals(vals.get(j))) return false;
i++;
j--;
}
return true;
}
}class Solution {
public:
bool isPalindrome(ListNode* head) {
vector<int> vals;
for (ListNode* p = head; p; p = p->next) vals.push_back(p->val);
int i = 0, j = (int)vals.size() - 1;
while (i < j) {
if (vals[i] != vals[j]) return false;
i++;
j--;
}
return true;
}
};func isPalindrome(head *ListNode) bool {
vals := []int{}
for p := head; p != nil; p = p.Next {
vals = append(vals, p.Val)
}
for i, j := 0, len(vals)-1; i < j; i, j = i+1, j-1 {
if vals[i] != vals[j] {
return false
}
}
return true
}var isPalindrome = function(head) {
const vals = [];
for (let p = head; p; p = p.next) vals.push(p.val);
let i = 0, j = vals.length - 1;
while (i < j) {
if (vals[i] !== vals[j]) return false;
i++;
j--;
}
return true;
};function isPalindrome(head: ListNode | null): boolean {
const vals: number[] = [];
for (let p = head; p; p = p.next) vals.push(p.val);
let i = 0, j = vals.length - 1;
while (i < j) {
if (vals[i] !== vals[j]) return false;
i++;
j--;
}
return true;
}