LeetCode 234: Palindrome Linked List (Linked List)
LeetCode 234Two PointersFast/SlowToday we solve LeetCode 234 - Palindrome Linked List.
Source: https://leetcode.com/problems/palindrome-linked-list/
English
Problem Summary
Given the head of a singly linked list, return true if the list values read the same forward and backward, otherwise return false.
Key Insight
Use fast/slow pointers to locate the midpoint, reverse the second half in-place, compare node values from both halves, then restore the list structure.
Brute Force and Limitations
Copy all node values into an array and check with two pointers from both ends. This is simple but costs O(n) extra memory, while the follow-up expects O(1) extra space.
Optimal Algorithm Steps
1) If list has 0 or 1 node, it is a palindrome.
2) Move slow by 1 and fast by 2 to find middle.
3) For odd length, skip the center node (if fast != null then slow = slow.next).
4) Reverse the list starting from slow.
5) Compare first half and reversed second half node by node.
6) Reverse second half again to restore original list.
Complexity Analysis
Time: O(n) (scan + reverse + compare + optional restore).
Space: O(1) extra space.
Common Pitfalls
- Forgetting to skip the middle node on odd-length lists.
- Breaking list links during reverse due to pointer update order.
- Not restoring list when interview/platform expects no mutation side effects.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
if (fast != null) { // odd length
slow = slow.next;
}
ListNode secondHead = reverse(slow);
ListNode secondCopy = secondHead;
ListNode first = head;
boolean ok = true;
while (secondHead != null) {
if (first.val != secondHead.val) {
ok = false;
break;
}
first = first.next;
secondHead = secondHead.next;
}
reverse(secondCopy); // restore list
return ok;
}
private ListNode reverse(ListNode node) {
ListNode prev = null;
while (node != null) {
ListNode next = node.next;
node.next = prev;
prev = node;
node = next;
}
return prev;
}
}func isPalindrome(head *ListNode) bool {
if head == nil || head.Next == nil {
return true
}
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
if fast != nil { // odd length
slow = slow.Next
}
second := reverse(slow)
secondCopy := second
first := head
ok := true
for second != nil {
if first.Val != second.Val {
ok = false
break
}
first = first.Next
second = second.Next
}
reverse(secondCopy) // restore
return ok
}
func reverse(node *ListNode) *ListNode {
var prev *ListNode
for node != nil {
next := node.Next
node.Next = prev
prev = node
node = next
}
return prev
}class Solution {
public:
bool isPalindrome(ListNode* head) {
if (!head || !head->next) return true;
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
if (fast) { // odd length
slow = slow->next;
}
ListNode* second = reverse(slow);
ListNode* secondCopy = second;
ListNode* first = head;
bool ok = true;
while (second) {
if (first->val != second->val) {
ok = false;
break;
}
first = first->next;
second = second->next;
}
reverse(secondCopy); // restore
return ok;
}
private:
ListNode* reverse(ListNode* node) {
ListNode* prev = nullptr;
while (node) {
ListNode* next = node->next;
node->next = prev;
prev = node;
node = next;
}
return prev;
}
};class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
if not head or not head.next:
return True
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if fast: # odd length
slow = slow.next
second = self._reverse(slow)
second_copy = second
first = head
ok = True
while second:
if first.val != second.val:
ok = False
break
first = first.next
second = second.next
self._reverse(second_copy) # restore
return ok
def _reverse(self, node: Optional[ListNode]) -> Optional[ListNode]:
prev = None
while node:
nxt = node.next
node.next = prev
prev = node
node = nxt
return prevvar isPalindrome = function(head) {
if (!head || !head.next) return true;
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
if (fast) { // odd length
slow = slow.next;
}
let second = reverse(slow);
const secondCopy = second;
let first = head;
let ok = true;
while (second) {
if (first.val !== second.val) {
ok = false;
break;
}
first = first.next;
second = second.next;
}
reverse(secondCopy); // restore
return ok;
};
function reverse(node) {
let prev = null;
while (node) {
const next = node.next;
node.next = prev;
prev = node;
node = next;
}
return prev;
}中文
题目概述
给你一个单链表头节点 head，判断该链表是否为回文链表（正着读和反着读一致），是则返回 true，否则返回 false。
核心思路
用快慢指针找到中点，把后半段原地反转，再与前半段逐个比较。比较完成后将后半段反转回来，避免修改原链表结构。
暴力解法与不足
暴力法是把链表值复制到数组，再双指针首尾比较。逻辑直观，但需要 O(n) 额外空间，不满足进阶要求。
最优算法步骤
1）链表长度为 0 或 1 时直接返回 true。
2）快慢指针同时出发，fast 每次走两步，slow 每次走一步。
3）若最终 fast != null，说明是奇数长度，slow 再前进一步跳过中间点。
4）从 slow 开始反转后半段。
5）前后两段同步比较节点值。
6）将后半段再次反转，恢复原链表。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)（仅使用常数额外指针）。
常见陷阱
- 奇数长度没跳过中间节点，导致比较错位。
- 反转链表时先后顺序写错，造成链表断裂。
- 只判断正确性但未恢复链表，可能影响后续逻辑。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
if (fast != null) { // odd length
slow = slow.next;
}
ListNode secondHead = reverse(slow);
ListNode secondCopy = secondHead;
ListNode first = head;
boolean ok = true;
while (secondHead != null) {
if (first.val != secondHead.val) {
ok = false;
break;
}
first = first.next;
secondHead = secondHead.next;
}
reverse(secondCopy); // restore list
return ok;
}
private ListNode reverse(ListNode node) {
ListNode prev = null;
while (node != null) {
ListNode next = node.next;
node.next = prev;
prev = node;
node = next;
}
return prev;
}
}func isPalindrome(head *ListNode) bool {
if head == nil || head.Next == nil {
return true
}
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
if fast != nil { // odd length
slow = slow.Next
}
second := reverse(slow)
secondCopy := second
first := head
ok := true
for second != nil {
if first.Val != second.Val {
ok = false
break
}
first = first.Next
second = second.Next
}
reverse(secondCopy) // restore
return ok
}
func reverse(node *ListNode) *ListNode {
var prev *ListNode
for node != nil {
next := node.Next
node.Next = prev
prev = node
node = next
}
return prev
}class Solution {
public:
bool isPalindrome(ListNode* head) {
if (!head || !head->next) return true;
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
if (fast) { // odd length
slow = slow->next;
}
ListNode* second = reverse(slow);
ListNode* secondCopy = second;
ListNode* first = head;
bool ok = true;
while (second) {
if (first->val != second->val) {
ok = false;
break;
}
first = first->next;
second = second->next;
}
reverse(secondCopy); // restore
return ok;
}
private:
ListNode* reverse(ListNode* node) {
ListNode* prev = nullptr;
while (node) {
ListNode* next = node->next;
node->next = prev;
prev = node;
node = next;
}
return prev;
}
};class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
if not head or not head.next:
return True
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if fast: # odd length
slow = slow.next
second = self._reverse(slow)
second_copy = second
first = head
ok = True
while second:
if first.val != second.val:
ok = False
break
first = first.next
second = second.next
self._reverse(second_copy) # restore
return ok
def _reverse(self, node: Optional[ListNode]) -> Optional[ListNode]:
prev = None
while node:
nxt = node.next
node.next = prev
prev = node
node = nxt
return prevvar isPalindrome = function(head) {
if (!head || !head.next) return true;
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
if (fast) { // odd length
slow = slow.next;
}
let second = reverse(slow);
const secondCopy = second;
let first = head;
let ok = true;
while (second) {
if (first.val !== second.val) {
ok = false;
break;
}
first = first.next;
second = second.next;
}
reverse(secondCopy); // restore
return ok;
};
function reverse(node) {
let prev = null;
while (node) {
const next = node.next;
node.next = prev;
prev = node;
node = next;
}
return prev;
}
Comments