Problem Statement
Palindrome Linked List
A linked list is a chain of boxes. Each box holds a value and a pointer to the next box. You can only walk it forward, one box at a time, starting from the front box called the head. A palindrome is a sequence that reads the same forward and backward, like 1, 2, 2, 1. The question: does this chain read the same in both directions? The easy trick would be to copy all the values into a normal list and check from both ends, but that uses extra memory. Instead we do it in place using three moves: find the middle box, flip the second half so it points backward, then walk the two halves toward each other and compare. This runs in O(n) time (we touch each box a fixed number of times) and O(1) space (no extra storage that grows with the list).
Signals to notice
Brute force first
Copy to array, two-pointer palindrome check — O(n) space.
The key insight
Find middle → reverse second half → compare both halves. O(n) time, O(1) space.
Trace it on head=[1,2,3,2,1]
start: slow=node(1), fast=node(1) find mid #1: slow=node(2), fast=node(3) (fast.next exists) find mid #2: slow=node(3), fast=node(1,last); fast.next=null -> stop, slow at middle(3) reverse from slow(3->2->1): prev now heads reversed half = 1->2->3 compare: left=head(1), right=prev(1) -> equal; advance compare: left(2), right(2) -> equal; left(3), right(3) -> equal; advance right reaches null -> loop ends, return true
What must stay true
After reversing the second half, parallel comparison from both heads reveals whether the list is a palindrome. Restore the list afterward if needed.
Shape of the loop
slow = fast = head while fast and fast.next: slow = slow.next; fast = fast.next.next // slow -> middle prev = reverse(slow) // reverse 2nd half in place left, right = head, prev while right: if left.val != right.val: return false; advance both return true
Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Odd-length lists — the middle element is irrelevant. Let one half be longer; comparison stops when the shorter half is exhausted.