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.
Intuition
You can't walk a singly linked list backwards. So find the middle, reverse the second half in place, then walk the two halves toward each other comparing values. Equal all the way means palindrome.
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
Find the middle with slow / fast
Run a slow pointer one step and a fast pointer two steps. When fast reaches the end, slow sits at the midpoint — the start of the second half. This is the same tortoise-and-hare trick used for 'Middle of the Linked List'.
Reverse the second half in place
From slow, reverse the rest of the list using the standard prev/curr pointer flip. Now you have two half-lists: the original front half (still pointing forward) and the reversed back half. No extra array is needed, so space stays O(1).
Walk both halves and compare
Advance one pointer from the head and one from the reversed second half, comparing values node by node. If any pair differs, return false immediately; if you exhaust the shorter half with all matches, it's a palindrome — return true. (The middle node in an odd-length list is ignored, which is correct.)
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.