Palindrome Linked List in O(1) Space: Split, Reverse, Compare

This one is a Easy-rated classic reported from Meta, Amazon, Microsoft interviews: "Palindrome Linked List". Like every post in this series, the goal is not memorizing the answer — it is recognizing the Fast and Slow Pointers pattern on sight. Part 5 of 11 in the Fast and Slow Pointers arc.

The Problem

Given the head of a singly linked list, return True if it reads the same forwards and backwards. Copying values to an array is O(n) space; the real question is the O(1)-space follow-up, which composes three list techniques into one solution.

Input:  1 -> 2 -> 2 -> 1
Output: True

Recognizing the Fast and Slow Pointers Pattern

Fast and slow pointers (Floyd's tortoise and hare) walk the same structure at different speeds. If there is a cycle they must meet; if there is not, the fast pointer finds the end in half the iterations — which also locates midpoints without knowing the length. It is the default tool for linked lists and for any sequence defined by repeatedly applying a function, all in O(1) space.

No backward pointers means you must manufacture the backward view. Fast and slow finds the midpoint; reversing the second half creates the reverse iterator; then a plain two-pointer comparison finishes. Recognizing the composition is the skill.

The Approach

Find the middle with fast and slow. Reverse from the middle onward using the standard three-pointer in-place reversal. Walk one pointer from the head and one from the new tail-head, comparing values; a mismatch is a fail. Odd lengths need no special case — the middle element compares against itself's side harmlessly.

Mention restoring the list (re-reverse) if the interviewer cares about non-destructive behavior; asking whether mutation is acceptable is itself a good look.

Python Solution

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


def is_palindrome_list(head: ListNode | None) -> bool:
    """True if the list is a palindrome. O(1) extra space."""
    if not head or not head.next:
        return True

    slow = fast = head
    while fast and fast.next:          # slow ends at second middle
        slow = slow.next
        fast = fast.next.next

    prev = None                        # reverse second half
    while slow:
        slow.next, prev, slow = prev, slow, slow.next

    left, right = head, prev
    while right:                       # second half is the shorter side
        if left.val != right.val:
            return False
        left = left.next
        right = right.next
    return True

Complexity

• Time: O(n) — three linear phases: midpoint, reversal, comparison
• Space: O(1) — in-place reversal, three pointers

Interview Tips and Follow-Ups

• The tuple-assignment reversal line is idiomatic Python but risky under pressure — the explicit three-variable version is safer live.
• Comparing while right (not left) is the odd-length trick: the reversed half is never longer. Know why.
• Recursion with an outer pointer also solves this in O(n) stack space — name it as the elegant-but-worse alternative.

That wraps part 5 of the Fast and Slow Pointers arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.