Palindrome Linked List
easyTime: O(n)Space: O(1)
Signals to notice
check if linked list reads same forward and backwardO(1) spacereverse half and compare
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.
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.
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.