Palindrome Linked List
Easy · Two Pointers · Linked List · Two Pointers · Stack · Recursion
Problem
Given the head of a singly linked list, return true if its values read the same forwards and backwards, and false otherwise.
Can you do it in O(n) time and O(1) extra space?
Examples
Input: head = [1,2,3,2,1] Output: true
Read backward, the values are the same 1, 2, 3, 2, 1.
Input: head = [4,5] Output: false
Read backward, the list is 5, 4.
Input: head = [7,0,0,7] Output: true
Two pairs of mirrored values and no middle node.
Constraints
- The list has between 1 and 10^5 nodes.
- 0 <= Node.val <= 9
Approaches
- Baseline: copy the values into an array — time O(n), space O(n)
Follow-up
The fast solution changes the list while it works. If other code may read the list at the same time, that is unsafe even though the list is restored at the end; the O(n)-space copy is then the safer choice. The use cases below reuse the middle-finding and reversing steps for other questions.
Related problems
Start free on Cariara · Coding problems · System design studio
