Palindrome Linked List

Palindrome Linked List is usually solved by using slow and fast pointers to reach the middle, reversing the second half, then comparing both halves node by node. That gives an $O(n)$ time solution with $O(1)$ extra space, which is the key follow-up target. The main execution risk is misplacing the middle on odd-length lists or comparing against an unreversed tail.

Problem Statement

You are given the head of a singly linked list and need to decide whether its values read the same forward and backward. Return true when the linked list forms a palindrome, and return false when the sequence breaks symmetry at any mirrored position.

For example, head = [1,2,2,1] should return true because the first half matches the reversed second half, while head = [1,2] should return false because the values differ immediately. The list length ranges from 1 to 10^5, node values are digits from 0 to 9, and the most interview-relevant version asks you to do this with linked-list pointer manipulation instead of copying everything into another structure.

Examples

Example 1

Input: head = [1,2,2,1]

Output: true

Example details omitted.

Example 2

Input: head = [1,2]

Output: false

Example details omitted.

Constraints

• The number of nodes in the list is in the range [1, 105].
• 0 <= Node.val <= 9

Solution Approach

Brute-force with an array copy

Traverse the linked list once, push each node value into an array, then use two indices from both ends to test whether the sequence is a palindrome. This is easy to code and easy to explain, but it ignores the main linked-list challenge because the real work is moved into array indexing rather than pointer manipulation.

Stack-based half comparison

Use slow and fast pointers to locate the midpoint while pushing values from the first half onto a stack. For odd lengths, skip the exact middle node, then compare the remaining nodes against stack pops. This keeps the logic closer to the list structure, but it still uses extra memory and can hide pointer mistakes until the midpoint handling breaks on odd-sized lists.

Optimal in-place reverse second half

Advance slow and fast pointers so slow lands at the middle boundary, reverse the second half of the list, and compare nodes from the front and from the reversed tail one by one. This is the standard LeetCode 234 answer because it achieves $O(n)$ time and $O(1)$ extra space. The trade-off is mutation: you must reverse carefully, handle odd versus even length correctly, and optionally restore the list if the interviewer asks for the original structure to remain unchanged.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The array-copy and stack approaches both run in $O(n)$ time and use $O(n)$ extra space because they store node values outside the list. The in-place midpoint-plus-reversal method also runs in $O(n)$ time, since each node is visited a constant number of times, but it uses only $O(1)$ extra space. In Palindrome Linked List, the important trade-off is not asymptotic time but whether you solve symmetry checking through true linked-list pointer manipulation or by avoiding the list structure with auxiliary storage.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.