Palindrome Linked List

A palindrome check on an array is one line. On a singly linked list you cannot walk backwards, so the O(1)-space answer needs three small routines working together. This problem tests whether you can compose techniques cleanly, and fast and slow pointers supply the first step.

The problem

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

• 3 → 5 → 8 → 5 → 3 → True. The middle value 8 has no partner, and that is fine.
• 3 → 5 → 5 → 4 → False. The first value is 3 and the last is 4.

Constraints: 1 to 10⁵ nodes, values 0 to 9. Follow-up: O(n) time and O(1) extra space.

Clarifying questions

• Can I change the list? Ask. The O(1) answer reverses half of it. Assume you may change it during the check but must put it back afterwards.
• Is an empty list a palindrome? Yes, and so is a single node.
• Compare values or nodes? Values.

Approach 1: copy into an array

Copy the values into a Python list, then compare the list with its reverse.

1def is_palindrome_with_list(head: ListNode | None) -> bool:2    """Copy the values into a Python list and compare it with its reverse."""3    values: list[int] = []4    while head is not None:5        values.append(head.val)6        head = head.next7    return values == values[::-1]

Time: O(n). Space: O(n) for the copy, plus another O(n) for the reversed slice.

This is the right first answer. It is simple and it cannot be wrong. It fails only the follow-up: with 10⁵ nodes it allocates two lists of 10⁵ values. A recursive version that compares on the way back up also uses O(n) space, on the call stack, and in Python it hits the default recursion limit of about 1,000.

The key insight

To compare the first value with the last, the second with the second-last, and so on, you need to walk the second half backwards. A singly linked list cannot do that, but you can make the second half point backwards by reversing it in place. That costs no extra memory.

So the plan is three routines you already know:

1. Find the end of the first half with fast and slow pointers, using the first-middle guard fast.next and fast.next.next.
2. Reverse the second half in place.
3. Walk both halves together, comparing values, until the second half runs out.

Then reverse the second half again to leave the list as you found it.

Approach 2: middle, reverse, compare

1def end_of_first_half(head: ListNode) -> ListNode:2    """First middle for even lengths; the end of the first half. Needs a non-empty list."""3    slow = fast = head4    while fast.next is not None and fast.next.next is not None:5        slow = slow.next6        fast = fast.next.next7    return slow8910def reverse(head: ListNode | None) -> ListNode | None:11    """Reverse a list in place and return the new head."""12    previous = None13    while head is not None:14        head.next, previous, head = previous, head, head.next15    return previous161718def is_palindrome(head: ListNode | None) -> bool:19    """O(1) extra space: find the middle, reverse the second half, compare, restore."""20    if head is None or head.next is None:21        return True22    first_end = end_of_first_half(head)23    second = reverse(first_end.next)24    left, right = head, second25    result = True26    while right is not None:27        if left.val != right.val:28            result = False29            break30        left, right = left.next, right.next31    first_end.next = reverse(second)       # put the list back as we found it32    return result

The one-line swap in reverse evaluates the right side first: it saves the old next, points the current node back at previous, and moves on. If that reads too densely, write the usual four lines with a next_node variable; it is the same algorithm.

Dry run on 3 → 5 → 8 → 5 → 3:

The middle node 8 belongs to the first half and never gets compared, which is right for an odd length.

Why the halves line up

The first-middle guard makes the split come out the same way every time. For an odd length 2m + 1, the first half gets m + 1 nodes (including the middle) and the second half gets m. For an even length 2m, both get m. So the second half is never longer than the first, and stopping when right runs out compares exactly m pairs: node 1 with node n, node 2 with node n − 1, and so on. On 3 → 5 → 8 → 5 → 3, m = 2, and the two comparisons are the two rows in the table.

The restore step matters more than it looks. After the reversal, first_end.next still points at the old first node of the second half, which is now the tail of the reversed part. Anyone who walks the list from head in that state sees 3 → 5 → 8 → 5 and then stops, a shorter list with the last node missing. Reversing again and reattaching with first_end.next = reverse(second) puts every pointer back.

On 3 → 5 → 5 → 4: first_end is the first 5, the second half 5 → 4 becomes 4 → 5, and the first comparison, 3 against 4, fails. Result False, and the list is restored.

Time: O(n). Finding the middle is n/2 ticks, each reversal n/2 steps, and the comparison n/2 steps. Space: O(1), a handful of pointers.

Edge cases

• Empty list or one node. Returned as True before end_of_first_half runs, which matters because that function reads head.next.
• Two nodes. first_end is the first node; the second half is one node. 1 → 1 gives True, 1 → 2 gives False.
• Even length. 3 → 5 → 5 → 3: first_end is the first 5, both halves have two nodes, and every node is compared once.
• Mismatch. Breaking out of the loop still reaches the restore line, so the list is put back even when the answer is False.

Follow-ups

• "Don't modify the list at all." Then you need O(n) space: the array, or a stack of the first half's values.
• "What if another thread reads the list during the check?" It would see a broken list. Say so; this is why many teams prefer the O(n)-space version in production code.
• "Reorder the list as first, last, second, second-last…" Same first two steps (split at the first middle, reverse the second half), then weave the halves together instead of comparing them.