Is a linked list a palindrome, in constant space?

Question

Given the head of a singly linked list, decide whether the sequence of values is a palindrome.

1 -> 2 -> 2 -> 1        -> True
1 -> 2 -> 3 -> 2 -> 1   -> True
1 -> 2                  -> False

Do it in $O(n)$ time and $O(1)$ extra space. Copying values into a Python list and comparing is $O(n)$ space; the point is to reuse the reversal trick.

Accepted Answer

Find the middle with a slow/fast pointer: when fast reaches the end, slow is at the midpoint. Reverse the second half in place using the standard three-pointer flip. Then walk the first half and the reversed second half in lockstep, comparing values. If every compared pair matches, it is a palindrome. The comparison stops when the (possibly shorter) reversed half runs out, which automatically ignores the odd middle element. Tracing 1 - 2 - 3 - 2 - 1: slow stops at the middle 3, the second half reverses to 1 - 2 - 3, and comparing 1,2 against 1,2 from the reversed side matches (the middle 3 is…

Is a linked list a palindrome, in constant space?

Your answer

More Coding questions