Palindrome Linked List
Given the head of a singly linked list, return true if it reads the same forwards and backwards — using O(1) extra space.
- The number of nodes in the list is in the range [1, 10⁵].
- 0 <= Node.val <= 9
Intuition
Palindrome linked list asks whether a singly linked list reads the same both ways, in O(1) extra space. That constraint is what makes it interesting — copying the values into an array and comparing with two pointers is trivial but costs O(n) memory. The difficulty is that a singly linked list cannot be walked backwards. There are no previous pointers, so comparing the first node against the last requires either storing everything or changing the list. The O(1) solution changes it. Three steps: - Find the middle, reverse the second half in place, then walk both halves inward comparing values. Finding the middle is the slow-and-fast pointer walk. Reversing is the standard three-pointer flip applied from the midpoint. Then one pointer starts at the head and another at the reversed tail, and equal values all the way means palindrome. The comparison loop should stop when the second half runs out, not the first. On an odd-length list the two halves differ by one node, and the middle element is its own mirror — it needs no partner and comparing past it would dereference null. One point of judgement worth raising rather than hiding: this mutates the input. If the caller still needs the original list, reverse the second half back before returning. Many solutions skip that restoration silently, and an interviewer may well ask about it.
Three techniques composed: find the middle with fast/slow, reverse the second half in place, then compare the halves. Each piece is a problem you already know — recognising a hard question as a composition of easy ones is the skill here, and it's what keeps this at O(1) space instead of copying to an array.
Approach
Before reading on: price up what the direct approach costs here, then ask which pointers must be saved before you overwrite anything. Aim for O(n) time and O(1) space.
Find the middle with slow and fast
Advance slow one node and fast two. When fast reaches the end, slow sits at the midpoint. This is the standard trick for locating the middle in one pass without knowing the length.
Reverse the second half in place
From the midpoint, apply the usual prev/curr flip so the second half points backwards. This is what makes the list traversable in reverse, which a singly linked list otherwise forbids.
Compare the two halves inward
Walk one pointer from the head and one from the reversed tail, comparing values. Any mismatch means the list is not a palindrome — return false immediately.
Stop when the second half ends
On an odd-length list the halves differ by one node. Looping until the second half runs out handles that automatically — the middle element is its own mirror and needs no comparison.
Consider restoring the list
The algorithm mutates the input. Reverse the second half back before returning if the caller still needs the original — many solutions skip this silently, and it is a fair follow-up question.
Cost of the approach
Finding the middle, reversing, and comparing are each O(n), giving O(n) time and O(1) space — against the O(n) space of copying values into an array, which is the trade this problem is testing.
Solution & live demo
Common pitfalls
Copying the values into a list
vals = [] while head: vals.append(head.val); head = head.next return vals == vals[::-1]
# find middle, reverse second half, compare
Correct and much simpler, but O(n) space — and the follow-up explicitly asks for O(1). The in-place version is the answer the question is testing for.
Comparing until both pointers are exhausted
while left and right:
while right:
On an odd-length list the two halves differ in length, so looping on the longer one walks off the end. The reversed second half is never longer, so it's the safe bound.
Reversing from head instead of the midpoint
prev = None while head: head.next, prev, head = prev, head, head.next
prev = None while slow: slow.next, prev, slow = prev, slow, slow.next
Reversing the whole list destroys the forward half you still need to compare against. Only the portion from the midpoint onward gets reversed.
Edge cases
Trivially a palindrome — return true.
For odd length the middle node is unpaired and safely skipped; comparison only spans the matched halves.
If the caller needs the list intact afterward, reverse the second half back; the comparison itself only needs it reversed.