What is the best approach for LeetCode 234 Palindrome Linked List?

The standard best approach is to find the middle with slow and fast pointers, reverse the second half in place, and compare the two halves node by node. That reaches $O(n)$ time and $O(1)$ extra space, which is usually the target follow-up answer.

Why use slow and fast pointers in this problem?

They let you locate the midpoint without first counting the nodes. In Palindrome Linked List, that matters because the whole in-place method depends on splitting the list at the correct boundary before reversing.

How do odd-length linked lists work here?

When the list has an odd number of nodes, the center node does not need a matching partner. After finding the middle, you skip that center position conceptually and compare only the nodes on each side of it.

Is using a stack acceptable for Palindrome Linked List?

Yes, a stack is a valid solution and still runs in $O(n)$ time. It is often accepted first, but it uses $O(n)$ extra space, so it is not the strongest answer when the interviewer wants linked-list pointer manipulation.

What is the main failure mode in the linked-list pointer manipulation pattern?

The biggest risk is getting the middle boundary wrong and reversing from the wrong node. That creates mismatched comparisons on even or odd lengths even when the list is actually a palindrome.

#234

Easy

auto_awesome链表指针操作

LeetCode 题解工作台

回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。示例 1：输入： head = [1,2,2,1] 输出： true 示例 2：输入： head = [1,2] 输出： false 提示：链表中节点数目在范围 [1, …

链表双指针栈递归

题目描述

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

链表中节点数目在范围[1, 10⁵] 内
0 <= Node.val <= 9

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

lightbulb

解题思路

方法一：快慢指针

我们可以先用快慢指针找到链表的中点，接着反转右半部分的链表。然后同时遍历前后两段链表，若前后两段链表节点对应的值不等，说明不是回文链表，否则说明是回文链表。

时间复杂度 $O(n)$ ，其中 $n$ 为链表的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head.next
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
        pre, cur = None, slow.next
        while cur:
            t = cur.next
            cur.next = pre
            pre, cur = cur, t
        while pre:
            if pre.val != head.val:
                return False
            pre, head = pre.next, head.next
        return True

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They mention a follow-up about constant extra space, which strongly points to reversing the second half in place.
question_mark
They ask how you would find the middle in one pass, signaling the slow and fast pointer setup.
question_mark
They probe odd-length behavior, which means they want to see whether you know when the middle node should be skipped.

warning

常见陷阱

外企场景

error
Starting comparison from the wrong middle position, especially on odd-length lists where the center node should not be matched against anything.
error
Reversing the list incorrectly by losing the next pointer, which breaks the second half before comparison even starts.
error
Comparing until the original tail length instead of the reversed half length, which can create false mismatches or null-pointer errors.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Restore the linked list after checking by reversing the second half back to its original order.
arrow_right_alt
Solve the same palindrome check recursively, using call stack depth to simulate symmetric traversal from both ends.
arrow_right_alt
Discuss a read-only interpretation where mutation is disallowed, making the stack or array approach the safer choice.

help

常见问题

外企场景

继续练习

#143 重排链表 #224 基本计算器 #160 相交链表