Palindrome Linked List (LeetCode 234)

The problem

You get the head of a singly linked list of integers. Return True if the values read the same forwards and backwards, otherwise False.

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

Input:  1 -> 2
Output: False

1 2 2 1 reversed is still 1 2 2 1. 1 2 reversed is 2 1, which is different.

How to think about it

Start with brute force. Copy the values into a Python list and check vals == vals[::-1]. That is O(n) time and O(n) space, and it is a perfectly good first answer. The follow-up asks for O(1) extra space, and that is where it gets interesting.

Why it is hard on a linked list. A palindrome check compares the first with the last, the second with the second-last, and so on. In an array you would use two pointers moving inwards. A singly linked list cannot walk backwards, so the right-hand pointer has nowhere to go.

The key insight: make the back half walk backwards by reversing it. Find the middle with fast and slow pointers. Reverse the list from the middle onwards, in place. Now you have two forward-walking lists: the front half from head, and the reversed back half from the old tail. Walk them together and compare values. If every pair matches, it is a palindrome.

Which pattern is this? Fast & slow pointers to find the middle, combined with in-place list reversal. The tell is “compare a linked list with its own mirror in O(1) space”.

Approach

1. Move s one step and f two steps until f runs out. s is now the middle (the second middle for even lengths).
2. Reverse the list starting at s, using the standard prev / next swap. prev ends on the old tail.
3. Walk l from head and r from prev together. Stop when r runs out, because the reversed half is never longer than the front half.
4. If any pair of values differs, return False. Otherwise return True.

Solution

def is_palindrome_list(head):
    s = f = head
    while f and f.next: s = s.next; f = f.next.next     # s = middle
    prev = None
    while s: s.next, prev, s = prev, s, s.next           # reverse from the middle
    l, r = head, prev                                    # front half vs reversed back half
    while r:
        if l.val != r.val: return False
        l = l.next; r = r.next
    return True
# is_palindrome_list([1,2,2,1]) -> True ; is_palindrome_list([1,2]) -> False

Dry run

On 1 -> 2 -> 2 -> 1:

On 1 -> 2, the middle is node 2, the reversed half is just 2, and the first comparison is 1 vs 2, so it returns False. On the odd list 1 2 3 2 1, the middle is 3 and the reversed half is 1 2 3; the middle node compares with itself.

Complexity

• Time: O(n). Finding the middle, reversing half, and comparing are each one linear pass.
• Space: O(1). Only a handful of pointers. The reversal reuses the existing nodes.

Edge cases and pitfalls

• Empty list or one node: always a palindrome. With head = None the comparison loop never runs and it returns True.
• The input is modified. After the call, the back half is reversed. If the caller still needs the list, reverse it back before returning. Mention this in an interview.
• Loop on r, not l. The front half still links into the middle node, so l can run longer than r. Stopping on r handles odd and even lengths.
• The tuple swap order matters. s.next, prev, s = prev, s, s.next evaluates the right side first, so it is safe. Rewriting it as three separate lines in the wrong order loses the rest of the list.

Related problems

• Middle of the Linked List (LeetCode 876): the first step of this solution on its own.
• Reverse Linked List (LeetCode 206): the reversal step on its own.
• Reorder List (LeetCode 143): the same middle-and-reverse set-up, followed by weaving instead of comparing.