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');



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

function findMidPoint(linkedList) {
  var slow = linkedList;
  var fast = linkedList;

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

  if (checkOdd(linkedList)) {
    return slow.next
  } else {
    return slow;
  }
}

function checkPalindrome(linkedList) {
  var midpoint = findMidPoint(linkedList);

  var firstHead = linkedList;
  var secondHead = reverseLL(midpoint);

  var flag = true;

  while (secondHead) {
    if (secondHead.val !== firstHead.val) {
      flag = false;
    }
    secondHead = secondHead.next;
    firstHead = firstHead.next;
  }
  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
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.