How do you check if a linked list is a palindrome in O(1) extra space?
Find the middle with slow and fast pointers, reverse the second half in place, then compare it with the first half node by node.
Explain it simply
You cannot walk a singly linked list backwards, so you cannot compare both ends directly. Fix that by making the second half run backwards: find the middle, reverse everything after it, and now you have two lists that should read identically if the whole list is a palindrome.
It is like folding a paper strip in half and checking that the two sides match.
Example
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
function fromArray(arr) {
const dummy = new ListNode(0);
let tail = dummy;
for (const v of arr) {
tail.next = new ListNode(v);
tail = tail.next;
}
return dummy.next;
}
function toArray(head) {
const out = [];
while (head) {
out.push(head.val);
head = head.next;
}
return out;
}
function isPalindrome(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
let prev = null;
while (slow) {
const next = slow.next;
slow.next = prev;
prev = slow;
slow = next;
}
let left = head;
let right = prev;
while (right) {
if (left.val !== right.val) return false;
left = left.next;
right = right.next;
}
return true;
}
console.log(isPalindrome(fromArray([1, 2, 3, 2, 1]))); // Output: true
console.log(isPalindrome(fromArray([1, 2, 3, 4]))); // Output: falseComplexity
Time O(n), space O(1).
What to say in the interview
"I locate the middle with two pointers, reverse the second half in place and compare it with the first half. Time is O(n) and extra space is O(1). I would mention that it changes the list, so I can reverse the half back afterwards if the list must stay intact."
Common mistakes
- Copying values into an array, which is fine but uses O(n) extra space when the question asks for O(1).
- Comparing past the middle of an odd-length list; the middle node needs no partner.