Linked List Palindrome Check: Three Approaches

A palindrome reads the same forwards and backwards. The string "racecar" is a palindrome. Checking this with a string or array is trivial — compare s[i] with s[n-1-i]. But a singly linked list has no backward traversal and no random access. That constraint forces us to think differently.

In this article we’ll build three solutions, each teaching a different technique that shows up repeatedly in linked list problems.

Problem statement

Given the head of a singly linked list, return True if the list is a palindrome, False otherwise.

LeetCode 234 — Palindrome Linked List

Examples:

1 -> 2 -> 2 -> 1        =>  True
1 -> 2 -> 3 -> 2 -> 1   =>  True
1 -> 2 -> 3             =>  False
1                        =>  True  (single node)
None                     =>  True  (empty list)

Node definition

Every solution below uses the same node class:

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

---

Approach 1: Stack-based (O(n) space)

Intuition

If we could compare the first half of the list against the reversed second half, we’d know immediately. A stack naturally reverses order — push every value, then walk the list a second time, popping and comparing.

Algorithm

1. Traverse the list once; push every value onto a stack.
2. Traverse the list a second time. At each node, pop from the stack and compare.
3. If every comparison matches, it’s a palindrome.

We only need to compare the first half against the stack (the second half reversed), but comparing the full list works just as well because a palindrome is symmetric.

Implementation

def is_palindrome_stack(head: ListNode) -> bool:
    # Step 1: Push all values onto a stack
    stack = []
    current = head
    while current:
        stack.append(current.val)
        current = current.next

    # Step 2: Walk the list again, comparing against reversed order
    current = head
    while current:
        if current.val != stack.pop():
            return False
        current = current.next

    return True

Walkthrough

List: 1 -> 2 -> 2 -> 1

Pass 1 — build stack:
  stack = [1, 2, 2, 1]

Pass 2 — compare:
  Node 1, pop 1  =>  match
  Node 2, pop 2  =>  match
  Node 2, pop 2  =>  match
  Node 1, pop 1  =>  match

All matched => True

Complexity

Metric	Value
Time	O(n) — two passes over the list
Space	O(n) — the stack stores every value

Optimization: half-stack

We can cut the stack in half. Use the slow/fast pointer trick to find the midpoint, then only push values from the second half:

def is_palindrome_half_stack(head: ListNode) -> bool:
    # Find the middle using slow/fast pointers
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Push second half onto stack
    stack = []
    while slow:
        stack.append(slow.val)
        slow = slow.next

    # Compare first half against stack
    current = head
    while stack:
        if current.val != stack.pop():
            return False
        current = current.next

    return True

This still uses O(n/2) = O(n) space, but in practice it uses half the memory.

---

Approach 2: Reverse second half (O(1) space)

Intuition

The key insight: reverse the second half of the list in-place, then compare the two halves node by node. This avoids any extra data structure.

Algorithm

1. Use slow/fast pointers to find the middle of the list.
2. Reverse the second half starting from slow.
3. Compare the first half and the reversed second half node by node.
4. (Optional) Restore the list by reversing the second half again.

Visual walkthrough

Original:    1 -> 2 -> 3 -> 2 -> 1

Step 1 — Find middle (slow lands on 3):
  First half:  1 -> 2
  Middle:      3
  Second half: 2 -> 1

Step 2 — Reverse second half starting from middle:
  1 -> 2 -> 3    1 -> 2 -> 3
                  |
  Reversed:       1 -> 2 -> 3 {'<'}- 2 {'<'}- 1

  Actually after reverse from node 3:
  second_half: 1 -> 2 -> 3 -> None
  But we reverse from slow:
  1 -> 2 -> 3 -> 2 -> 1
       ^slow      
  reverse from slow.next:
  second_half_reversed: 1 -> 2 -> None

Step 3 — Compare:
  p1: 1 -> 2 -> ...
  p2: 1 -> 2 -> None
  Node 1 == Node 1  =>  match
  Node 2 == Node 2  =>  match
  p2 is None => done => True

Implementation

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

    # Step 1: Find the middle
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Step 2: Reverse the second half
    prev = None
    current = slow
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    # prev is now the head of the reversed second half

    # Step 3: Compare both halves
    left = head
    right = prev
    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next

    return True

Why this works for odd-length lists

For a list of length 5 like 1 -> 2 -> 3 -> 2 -> 1:

After finding middle, slow is at node 3.
Reversed second half: 1 -> 2 -> 3 -> None

First half comparison:  1, 2
Second half comparison: 1, 2, 3

We compare until the shorter half (left side) is exhausted.
Actually, right pointer exhausts first or both at same time.
The middle element (3) compares against itself — always matches.

Restoring the list (optional)

In interviews, they may ask you to restore the original list. Just reverse the second half again after comparing:

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

    # Find middle
    slow = fast = head
    prev_slow = None
    while fast and fast.next:
        prev_slow = slow
        slow = slow.next
        fast = fast.next.next

    # Reverse second half
    prev = None
    current = slow
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    second_half_head = prev

    # Compare
    result = True
    left, right = head, second_half_head
    while right:
        if left.val != right.val:
            result = False
            break
        left = left.next
        right = right.next

    # Restore: reverse the second half back
    prev = None
    current = second_half_head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node

    return result

Complexity

Metric	Value
Time	O(n) — find middle O(n/2) + reverse O(n/2) + compare O(n/2)
Space	O(1) — only pointer variables

This is the optimal solution in terms of space.

---

Approach 3: Recursive

Intuition

Recursion naturally reaches the end of the list first (base case), then unwinds. If we keep a front pointer that advances during the unwinding, we can compare the front and back simultaneously.

Algorithm

1. Maintain a front pointer starting at head.
2. Recurse to the end of the list.
3. During unwinding, compare front.val with the current node’s val.
4. Advance front after each comparison.

Implementation

def is_palindrome_recursive(head: ListNode) -> bool:
    front = [head]  # Use a list to allow mutation in nested scope

    def check(node):
        if node is None:
            return True

        # Recurse to the end
        if not check(node.next):
            return False

        # Compare front with current (unwinding from the end)
        if front[0].val != node.val:
            return False

        # Advance front pointer
        front[0] = front[0].next
        return True

    return check(head)

Walkthrough

List: 1 -> 2 -> 2 -> 1
front starts at node 1

Recursion goes deep:
  check(1) -> check(2) -> check(2) -> check(1) -> check(None)

Unwinding:
  check(None) returns True
  check(1): front=1, node=1 => match, advance front to 2
  check(2): front=2, node=2 => match, advance front to 2
  check(2): front=2, node=2 => match, advance front to 1
  check(1): front=1, node=1 => match => True

Complexity

Metric	Value
Time	O(n) — visit each node once
Space	O(n) — recursion call stack depth

The recursive approach is elegant but uses O(n) stack space — the same as the stack-based approach. Its main value is as a teaching tool for understanding recursion on linked lists.

---

Comparison of all three approaches

Approach	Time	Space	Modifies list?	Best for
Stack	O(n)	O(n)	No	Simplicity, quick implementation
Reverse second half	O(n)	O(1)	Yes (restorable)	Optimal space, interviews
Recursive	O(n)	O(n)	No	Understanding recursion

For interviews, Approach 2 (reverse second half) is the gold standard. Interviewers want to see:

• Slow/fast pointer technique
• In-place list reversal
• Careful handling of odd vs even lengths

Edge cases to handle

# Empty list
assert is_palindrome_reverse(None) == True

# Single node
n1 = ListNode(1)
assert is_palindrome_reverse(n1) == True

# Two nodes — palindrome
n1 = ListNode(1, ListNode(1))
assert is_palindrome_reverse(n1) == True

# Two nodes — not palindrome
n1 = ListNode(1, ListNode(2))
assert is_palindrome_reverse(n1) == False

Common mistakes

1. Off-by-one with slow/fast pointers. When fast can move two steps, slow moves one. For even-length lists, slow ends up at the start of the second half. For odd-length, slow is at the exact middle.

2. Not handling even vs odd lengths. The reverse approach naturally handles both, but be careful if you try to split the list explicitly.

3. Forgetting to restore the list. If the problem says “do not modify the input,” you need to reverse the second half back after comparing.

4. Stack comparison going too far. When using the half-stack approach, make sure you only compare n/2 elements.

Practice problems

Problem	Difficulty	Link
Palindrome Linked List	Easy	LeetCode 234
Palindrome Number	Easy	LeetCode 9
Valid Palindrome	Easy	LeetCode 125
Reverse Linked List	Easy	LeetCode 206
Middle of the Linked List	Easy	LeetCode 876

Key takeaways

• The slow/fast pointer pattern is essential for linked list problems — it finds the middle in one pass without knowing the length.
• In-place reversal of a sublist is a building block you’ll use over and over. Practice it until it’s second nature.
• When an interviewer asks for O(1) space on a linked list problem, think about whether you can restructure the list itself to avoid extra storage.
• The recursive approach teaches you how the call stack can act as implicit storage — useful for many tree and list problems.

Next, we’ll look at another classic linked list problem: removing the nth node from the end using a similar two-pointer gap technique.