Given the head of a singly linked list, return true if the list reads the same forwards and backwards, and false otherwise.
Your function receives a ListNode chain; the examples show each list in array notation for readability — [1, 2, 2, 1] is the chain 1 -> 2 -> 2 -> 1, which is a palindrome.
Aim for O(n) time and O(1) extra space.
Example
Reads the same both ways.
Constraints
- The number of nodes in the list is in the range [1, 100000].
- 0 <= Node.val <= 9
Intuition
A palindrome reads the same both ways, so the simplest check copies every value into an array and compares it against its reverse with two indices closing in from the ends.
function isPalindrome(head) {
// Copy the values out so we can index from both ends.
const values = [];
for (let node = head; node; node = node.next) values.push(node.val);
// Two pointers converging — the classic palindrome check.
let left = 0;
let right = values.length - 1;
while (left < right) {
if (values[left] !== values[right]) return false;
left++;
right--;
}
return true;
}That's a clean O(n) check, but it spends O(n) extra space on the array. Can we do better and use O(1) space, working on the list itself?
The key observation: to compare the front half against the back half we need to read the back half forward. A list only goes one way — so reverse the back half in place, then walk the two halves toward the middle.
Two sub-techniques combine here, both from the Two pointers toolkit: fast/slow finds the midpoint (fast moves two nodes per one of slow, so when fast hits the end, slow is at the middle), and the three-pointer reversal flips the second half. Then compare the original front with the reversed back in lockstep.
Note on the model: in the stored solution slow does double duty — first as the midpoint finder, then it's consumed by the reversal loop, leaving prev as the head of the reversed back half (the right walker below). Walking it through on 1 -> 2 -> 2 -> 1:
is 1 -> 2 -> 2 -> 1 a palindrome?
Both start at the head. fast will move twice as fast as slow to locate the midpoint.
One step: slow → index 1, fast → index 2. fast.next is the last node, so the loop stops next.
slow lands at index 2, the start of the back half (indices 2..3). Now reverse from here.
The back half is reversed: index 3 now points to index 2. `right` heads it; `left` is the original head.
Compare in lockstep: left value 1 == right value 1, then 2 == 2. The reversed half ends — all matched → palindrome.
Optimization
Find middle, reverse second half, compare
A palindrome reads the same from both ends, so compare the front half against the back half. To do that in O(1) extra space, work in place.
First find the middle with the slow/fast (tortoise/hare) trick: fast moves two nodes for every one of slow, so when fast runs off the end, slow sits at the midpoint. Reverse the second half starting from slow using the standard three-pointer rewire. Then walk the original front and the reversed back in lockstep — if any pair of values differs, it isn't a palindrome.
For an odd-length list the exact middle node is shared by both halves and never needs to match, so the lockstep comparison (which stops when the shorter, reversed half ends) handles it for free.
O(n) time (find + reverse + compare are each one pass), O(1) space.
function isPalindrome(head) {
// Step 1: find the midpoint. fast moves twice as fast as slow,
// so slow lands on the start of the second half.
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
// Step 2: reverse the second half (everything from slow onward).
let prev = null;
while (slow) {
const next = slow.next;
slow.next = prev;
prev = slow;
slow = next;
}
// Step 3: walk the front half and the reversed back half together.
// prev heads the reversed back half; it's the shorter side on odd lengths.
let left = head;
let right = prev;
while (right) {
if (left.val !== right.val) return false;
left = left.next;
right = right.next;
}
return true;
}Complexity analysis
Time complexity: O(n). Here's why:
- Finding the midpoint with fast/slow is one pass over
nnodes. - Reversing the second half touches each of those nodes once.
- The final lockstep comparison walks the two halves once.
Three sequential linear passes is still O(n) — no nesting.
Space complexity: O(1). Here's why:
- The midpoint, reversal, and comparison each use only a handful of pointers.
- The second half is reversed in place rather than copied.
This is the improvement over the array-dump brute force, which spends O(n) on the values array.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| head = [1]1null | true | Single node — trivially a palindrome. |
| head = [1,2]12null | false | Two distinct values — reversing gives 2 -> 1, which differs. |
| head = [1,1]11null | true | Two equal values — the smallest even palindrome. |
| head = [1,2,1]121null | true | Odd length — the lone middle node never needs to match. |
| head = [1,2,2,1]1221null | true | Even-length palindrome — both halves mirror exactly. |
| head = [1,2,3,4,2,1]123421null | false | Looks symmetric at the ends but breaks in the middle (3 vs 4). |
Try it yourself
Write your solution against the real judge before checking the reference.