# Check if a linked list is a palindrome in O(n) time and O(1) space

I liked this problem because there are so many sub-problems that are interview problems in their own right-- (reverse linked list, find midpoint)

var Node = function(val) {
this.val = val;
this.next = null;
}

var a = new Node('r');
var b = a.next = new Node('a');
var c = b.next = new Node('c');
var d = c.next = new Node('e');
var e = d.next = new Node('c');
var f = e.next = new Node('a');
var g = f.next = new Node('r');

var count = 0;
var curr = linkedList;
while (curr) {
count++;
curr = curr.next;
}
return count % 2 === 1;
}

var slow = linkedList;
var fast = linkedList;

while (fast && fast.next) {
fast = fast.next.next;
slow = slow.next
}

return slow.next
} else {
return slow;
}
}

var midpoint = findMidPoint(linkedList);

var secondHead = reverseLL(midpoint);

var flag = true;

flag = false;
}
}
return flag;
}

function reverseLL(root) {
var prevNode = null;
var currNode = root;
var nextNode;
while (currNode) {
nextNode = currNode.next;
currNode.next = prevNode;
prevNode = currNode;
currNode = nextNode;
}
return prevNode;
}

console.log(checkPalindrome(a)); = true


• checkOdd is unwarranted waste of time. You may deduce evenness of the list just by looking at fast: if it is null the list is even.

• flag is a meaningless name. Failure to come up with a good name typically indicates that you'd be better off without such variable. Consider return false; as soon as a mismatch is found, and return true at the end of the function.

• Yeah checkOdd is a waste of time now that I look at it more closely, thanks! Commented Dec 29, 2015 at 21:35
• Failure to come up with a good name typically indicates that you'd be better off without such variable. Not necessarily, my variable naming is awful regardless of the functions they have.
– Mast
Commented Dec 29, 2015 at 21:43

I agree that your code runs in $O(n)$ time and $O(1)$ space complexity, but the issue I have is that you do in-place modification of the list..... and thus a "processed" list is no longer the same list as it started as.

This makes the function useless for most practical purposes. A list that returns "true" on one call, will likely not return "true" on the second call.

A compromise solution would be to restore the list linking after reversing the second half, but your method will still not be reentrant - even though it would be more convenient to use.

In other words, you are using the list itself as a place to store temporary "state", and that list is not entirely contained in your function. This is as bad, or worse, than using global variables.

In a real interview I would challenge the requirement to have the $O(1)$ space, and suggest that $O(n)$ space is an acceptable compromise - or that a double-linked list is a better data structure to contain this problem.