Palindrome Linked List
The key idea
You only need to compare the first half against the reversed second half. Find the middle with a slow/fast pointer (
fast moves twice as fast, so when it reaches the end slow sits at the midpoint), reverse the half after slow in place, then walk one pointer from the front and one from the new reversed half — if every pair matches, it is a palindrome. This runs in O(n) time using only a constant number of pointers.Problem
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
A list is a palindrome when the sequence of node values reads the same forward and backward. Try to solve it in O(n) time using only O(1) extra space.
Constraints
- The number of nodes in the list is in the range
[1, 10^5]. 0 <= Node.val <= 9
Examples
Input: head = [1,2,2,1]
Output: true
Input: head = [1,2]
Output: false
Input: head = [1,2,3,2,1]
Output: true
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization