214. Palindrome Linked List
You are handed head, the first node of a singly linked list of digits. Decide whether the stored sequence is a palindrome — the same whether you read it head-to-tail or tail-to-head — and return true or false.
So 1 → 2 → 2 → 1 qualifies, while 1 → 2 does not.
Copying the values out into an array makes the check trivial, and that is a perfectly good first solution. The version interviewers care about is the follow-up: the list only lets you walk forward, so can you still answer in O(n) time with only O(1) extra space?
Example 1:
Input: head = [1, 2, 2, 1]
Output: true
Explanation: Read backwards the list is still 1, 2, 2, 1 — every position matches its mirror.
Example 2:
Input: head = [1, 2]
Output: false
Explanation: Backwards it reads 2, 1, which differs from 1, 2 at the very first node.
Constraints:
- 1 ≤ number of nodes ≤ 10⁵
- 0 ≤ node value ≤ 9
Hints:
Dump the values into an array (or push the first half onto a stack) and compare with two indices closing in from the ends. Correct, O(n) time — but O(n) extra space.
For O(1) space: advance a fast pointer two steps per one step of a slow pointer; when fast falls off the end, slow sits at the start of the back half. Reverse that back half in place, then walk one cursor from the head and one from the new front of the reversed half, comparing values as you go.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: head = [1, 2, 2, 1]
Expected output: true