Palindrome Linked List
easyTime: O(n)Space: O(1)
Recognize the pattern
check if linked list reads same forward and backwardO(1) spacereverse half and compare
Brute force idea
Copy to array, two-pointer palindrome check — O(n) space.
Better approach
Find middle → reverse second half → compare both halves. O(n) time, O(1) space.
Key invariant
After reversing the second half, parallel comparison from both heads reveals whether the list is a palindrome. Restore the list afterward if needed.
Watch out for
Odd-length lists — the middle element is irrelevant. Let one half be longer; comparison stops when the shorter half is exhausted.