Palindrome Linked List: Fast-Slow + Reverse

Palindrome Linked List is LeetCode 234. It combines two fundamental linked list techniques into one clean solution: the fast slow pointer to find the midpoint, and in-place reversal to flip the second half. If you know those two building blocks, this problem is straightforward. If you do not, it will feel impossible.

The brute force (copy values into an array, check if the array is a palindrome) works fine but costs O(n) space. The follow-up asks: can you do it in O(1) space? That is the version interviewers care about, and it is the version we will build here.

The problem

You are given the head of a singly linked list. Return true if the list is a palindrome, false otherwise.

A palindrome reads the same forwards and backwards. So 1 -> 2 -> 2 -> 1 is a palindrome, but 1 -> 2 -> 3 -> 1 is not.

Why this is harder than it looks

With a string or array, checking for a palindrome is trivial: compare the first element to the last, second to second-to-last, and so on. Two pointers from each end, moving inward. Done in O(1) extra space.

Linked lists do not give you that. You cannot index from the back. You cannot move backwards. You are stuck going forward, one node at a time.

So you need a plan. And the plan has three phases:

1. Find the middle of the list using the fast slow pointer technique
2. Reverse the second half in place
3. Compare the first half to the reversed second half, node by node

If every pair matches, it is a palindrome. If any pair does not match, it is not.

Phase 1: Find the middle

This is the classic tortoise-and-hare setup. Use a slow pointer that moves one step at a time and a fast pointer that moves two steps at a time. When fast reaches the end of the list, slow will be sitting at the middle.

For even-length lists like 1 -> 2 -> 2 -> 1, slow ends up at the start of the second half (the second 2). For odd-length lists like 1 -> 2 -> 3 -> 2 -> 1, slow ends up at the center node (3), and slow.next is the start of the second half.

Either way, slow gives you the split point.

Phase 2: Reverse the second half

Starting from slow, reverse the remaining nodes in place. This is the exact same three-pointer technique from Reverse Linked List: save next, flip the arrow, advance prev and curr.

After reversal, the second half of the list now runs backwards. Its head is what used to be the tail of the original list.

Phase 3: Compare

Walk two pointers simultaneously: one from the head of the original list, one from the head of the reversed second half. Compare values at each step. If you find a mismatch, return false. If you get through the entire second half without a mismatch, return true.

Visual walkthrough

Let's trace through checking whether 1 -> 2 -> 2 -> 1 is a palindrome. Watch how we find the middle, reverse the back half, and then compare.

Every pair matched: 1 == 1 and 2 == 2. It is a palindrome.

The solution

def isPalindrome(head):
    # Phase 1: find the middle
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Phase 2: reverse the second half
    prev = None
    curr = slow
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    # Phase 3: compare both halves
    left = head
    right = prev  # prev is the head of the reversed second half
    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next

    return True

Three loops, each doing one job. No extra data structures, no recursion, no tricks. Just pointers.

Complexity analysis

Time: O(n). Each phase does a single pass through part of the list. Finding the middle is O(n/2), reversing is O(n/2), comparing is O(n/2). That is O(n) total.

Space: O(1). We only use a handful of pointer variables. No array copy, no hash set, no stack. This is the whole point of the fast-slow-plus-reverse approach.

Edge cases

• Empty list (head is null). An empty list is a palindrome. fast is null, the while loop never runs. The comparison loop never runs. Return true. Correct.
• Single node. Trivially a palindrome. Same logic as above.
• Two nodes, same value. slow ends at the second node after one iteration. Reverse it (it points to null). Compare: left.val == right.val. Return true.
• Two nodes, different values. Same flow, but the comparison fails. Return false.
• Odd-length palindrome like 1 -> 2 -> 1. slow lands on 2. After reversal, the right half is 1 -> 2. We compare left = 1 with right = 1 (match), then right.next is 2, but we only compare while right is not null and walk both pointers. Actually, right becomes 2 and left becomes 2, which match. Then right.next is null, loop ends. Correct.

The Building Blocks

This problem is built from two core building blocks:

Fast-slow pointer. Two pointers moving at different speeds through the list. When the fast pointer reaches the end, the slow pointer is at the midpoint. This is the same technique used in Linked List Cycle (Floyd's algorithm) and Middle of the Linked List (LeetCode 876). The speed difference gives you structural information about the list without counting nodes first.

In-place linked list reversal. The three-pointer dance: save next, flip the arrow, advance. This is the technique from Reverse Linked List (LeetCode 206). You do not need to reverse the entire list here, just from the midpoint to the end. But the mechanics are identical.

These two bricks combine naturally. Fast-slow gives you the midpoint, reversal lets you compare from both ends without extra space. Together they solve what would otherwise require O(n) memory.

This same combination shows up in other problems:

• Reorder List (LeetCode 143) uses fast-slow to find the middle, reversal to flip the back half, then interleaves the two halves. Almost the exact same setup as palindrome linked list, with a different final phase.
• Sort List (LeetCode 148) uses fast-slow to split the list for merge sort. Not reversal, but the midpoint-finding phase is identical.

Once you have both bricks drilled into memory, the palindrome linked list problem becomes an assembly exercise. You are not solving it from scratch. You are snapping two known pieces together.

Why you will forget this (and how to fix it)

This problem has three phases, and each phase has its own set of pointer variables. That is a lot of state to keep in your head during an interview. The most common mistakes:

• Forgetting to handle the fast and fast.next loop condition correctly
• Reversing from the wrong starting point
• Comparing with while left instead of while right and running into a null pointer

The fix is repetition. Not reading the solution again. Typing it from scratch, from memory, with no reference. The first time you will stall somewhere. The second time it flows more smoothly. By the third or fourth rep, your hands just know the three-loop structure.

Related posts

• Reverse Linked List - The core reversal technique used in phase 2 of this solution
• Linked List Cycle - The fast slow pointer technique used in phase 1 to find the midpoint