1
\$\begingroup\$

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 && 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
\$\endgroup\$

2 Answers 2

3
\$\begingroup\$
  • 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.

\$\endgroup\$
2
  • \$\begingroup\$ Yeah checkOdd is a waste of time now that I look at it more closely, thanks! \$\endgroup\$ Commented Dec 29, 2015 at 21:35
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Mast
    Commented Dec 29, 2015 at 21:43
4
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.