Check If a Linked List Is a Palindrome: Stack, Reverse-Half, Recursive

Check If a Linked List Is a Palindrome: Stack, Reverse-Half, and Recursive Approaches

Palindrome linked list (LeetCode #234) is a classic interview question that tests whether you can adapt array-style palindrome thinking to a structure where you can’t index backwards. The naive solution (copy to array) gives O(n) time and O(n) space; the elegant solution (reverse the second half in place) gives O(n) time and O(1) space, which is what most interviewers want. This guide covers both, with working code, the reversal trick, and the recursive variant.

Problem Statement

Given the head of a singly linked list, return True if the list reads the same forwards and backwards, False otherwise.

Examples:

• 1 → 2 → 2 → 1 → True
• 1 → 2 → False
• 1 → 2 → 1 → True (odd-length palindrome)
• 1 → True

Approach 1: Copy to Array (O(n) Space)

Convert to a list, then check using two pointers. Easiest to write; O(n) extra space.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def is_palindrome_array(head: ListNode) -> bool:
    """O(n) time, O(n) space."""
    values = []
    while head:
        values.append(head.val)
        head = head.next
    return values == values[::-1]

Acceptable as a warm-up; interviewers will push for O(1) space.

Approach 2: Reverse Second Half (Standard Answer, O(1) Space)

Find the middle, reverse the second half, then compare halves node-by-node. This achieves O(n) time and O(1) space without modifying the input destructively (you can restore the second half before returning if needed).

def is_palindrome(head: ListNode) -> bool:
    """O(n) time, O(1) space."""
    if not head or not head.next:
        return True

    # Phase 1: find middle (slow ends at middle for odd, end-of-first-half for even)
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    # Phase 2: reverse the second half
    second_half = reverse(slow.next)

    # Phase 3: compare halves
    p1, p2 = head, second_half
    while p2:
        if p1.val != p2.val:
            return False
        p1 = p1.next
        p2 = p2.next
    return True


def reverse(head: ListNode) -> ListNode:
    """Standard linked-list reversal."""
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

Complexity: O(n) time (three linear passes), O(1) space (just pointers).

Why this works

After phase 1, slow points to the middle of the list (the last node of the first half for odd length; the last node of the first half for even length, which is the same as “node n/2 from the start”). Reversing the second half makes it walkable from the end backwards. Comparing forward through both halves checks palindrome property.

The two halves don’t have to be exactly equal in length:

• Even length n: first half has n/2 nodes, second half has n/2 nodes.
• Odd length n: first half has (n+1)/2 nodes (including middle), second half has (n-1)/2 nodes. The middle is in the first half and naturally gets skipped in the comparison loop because we exit when p2 is None.

Approach 3: Recursive (O(n) Space, but Conceptually Different)

Use recursion to walk to the end. As the call stack unwinds, compare the unwinding pointer to a forward pointer. O(n) space due to call stack; useful when the interviewer asks for a recursive solution.

def is_palindrome_recursive(head: ListNode) -> bool:
    """O(n) time, O(n) space (recursion)."""
    front = [head]

    def check(node: ListNode) -> bool:
        if not node:
            return True
        if not check(node.next):
            return False
        if front[0].val != node.val:
            return False
        front[0] = front[0].next
        return True

    return check(head)

The trick: the recursion lets you walk backwards through the list “for free” by leveraging the call stack. The mutable container front tracks the forward pointer across recursive calls. Elegant but uses O(n) stack space.

Restoring the List After Reversal

The reverse-second-half approach mutates the input. If the caller expects the list unchanged, restore it before returning:

def is_palindrome_restoring(head: ListNode) -> bool:
    if not head or not head.next:
        return True

    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    second_half = reverse(slow.next)
    second_head = second_half  # save for restoration

    p1, p2 = head, second_half
    result = True
    while p2:
        if p1.val != p2.val:
            result = False
            break
        p1 = p1.next
        p2 = p2.next

    # Restore: reverse second half back
    slow.next = reverse(second_head)
    return result

Strong candidates mention this when discussing the trade-off; some interviewers explicitly require non-destructive solutions.

Common Variations

Doubly linked list palindrome check

Trivial: walk forward and backward simultaneously with two pointers. O(n) time, O(1) space, no reversal needed.

Palindrome with comparison key

Sometimes you compare a derived value (e.g., parity, hash) rather than the raw value. Same algorithm; replace p1.val != p2.val with the appropriate comparison.

Find the middle of a linked list

(LeetCode #876) Standalone problem. The fast/slow pointer trick used here is the canonical answer.

Reverse a linked list

(LeetCode #206) The reverse helper used here is itself a classic interview question. Often asked together as a sequence: “reverse a linked list” → “find the middle” → “check if palindrome.”

Common Mistakes

• Off-by-one in finding the middle. The condition while fast.next and fast.next.next places slow at the end of the first half. while fast and fast.next places slow one step further (start of second half for even-length lists). Pick one consistently and verify with examples.
• Forgetting empty-list and single-node cases. Both are palindromes by convention. Early return prevents null-pointer issues in the rest of the algorithm.
• Not reversing the second half before comparing. Without reversal, you’re checking equality of two halves, which is a different property than palindrome.
• Modifying the input without restoring. If the interviewer cares about preserving the list, mutating it is a bug. Ask whether mutation is acceptable; restore if needed.
• Comparing pointers instead of values. p1 == p2 compares node identity, not value. Use p1.val != p2.val for the palindrome check.

Frequently Asked Questions

See also: Detect a Cycle in a Linked List • Reverse a Doubly Linked List • Longest Palindromic Substring

class ListNode {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

function isPalindrome(head) {
    if (!head || !head.next) return true;

    // Step 1: Find middle using slow/fast pointers
    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // slow is now at the middle
    // Step 2: Reverse second half
    let secondHalf = reverseList(slow);

    // Step 3: Compare first and second half
    let firstHalf = head;
    while (secondHalf) {
        if (firstHalf.val !== secondHalf.val) {
            return false;
        }
        firstHalf = firstHalf.next;
        secondHalf = secondHalf.next;
    }

    return true;
}

function reverseList(head) {
    let prev = null;
    let current = head;

    while (current) {
        let next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }

    return prev;
}

// Test cases
// Create list: 1->2->2->1
let head1 = new ListNode(1);
head1.next = new ListNode(2);
head1.next.next = new ListNode(2);
head1.next.next.next = new ListNode(1);

console.log(isPalindrome(head1));  // true

// Create list: 1->2->3
let head2 = new ListNode(1);
head2.next = new ListNode(2);
head2.next.next = new ListNode(3);

console.log(isPalindrome(head2));  // false

function isPalindromeStack(head) {
    let stack = [];
    let slow = head;
    let fast = head;

    // Push first half onto stack
    while (fast && fast.next) {
        stack.push(slow.val);
        slow = slow.next;
        fast = fast.next.next;
    }

    // If odd length, skip middle
    if (fast) slow = slow.next;

    // Compare second half with stack
    while (slow) {
        if (stack.pop() !== slow.val) {
            return false;
        }
        slow = slow.next;
    }

    return true;
}