Mad Max of Palindrome

The goal today is to write a function that evaluates a linkedlist to determine whether it contains a palindrome using O(n) time and O(1) space. We will do this by writing an palindrome function that evaluates the expression using the existing reverseLinkedList method.

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

function LinkedList(headValue) {
  if (headValue === undefined) console.log('Must provide value for first node');
  this.head = new Node(headValue);
  this.tail = this.head;
}

LinkedList.prototype.forEach = function(callback) {
  var node = this.head;
  while (node) {
    callback(node.value);
    node = node.next;
  }
};

LinkedList.prototype.print = function() {
  var result = [];
  this.forEach(function(value) {
    result.push(value);
  });
  return result.join(', ');
};

LinkedList.prototype.insertAfter = function(node, value) {
  // get reference to former next
  var oldNext = node.next;
  // create new node
  var newNext = new Node(value);
  // store it as the new next
  node.next = newNext;
  // set next for the new node to be the old next
  newNext.next = oldNext;
  // if reference node is tail, set tail to newNext
  if (this.tail === node) this.tail = newNext;
  return newNext;
};

LinkedList.prototype.removeAfter = function(node) {
  // store reference to removed node
  var removedNode = node.next;
  // if node is tail, then there's nothing to remove
  if (!removedNode) return 'Nothing to remove';
  // get reference to node after removed node
  var newNext = removedNode.next;
  // set newNext as the next node
  node.next = newNext;
  // remove reference from removed node to linked list
  removedNode.next = null;
  // if removedNode is tail, set tail to node
  if (removedNode === this.tail) this.tail = node;
  return removedNode;
};

LinkedList.prototype.insertHead = function(value) {
  var newHead = new Node(value);
  var oldHead = this.head;
  this.head = newHead;
  newHead.next = oldHead;
  return this.head;
};

LinkedList.prototype.removeHead = function() {
  var oldHead = this.head;
  var newHead = oldHead.next;
  this.head = newHead;
  oldHead.next = null;
  return oldHead;
}

LinkedList.prototype.findNode = function(value) {
  var node = this.head;
  while (node) {
    if (node.value === value) return node;
    node = node.next;
  }
  return 'No node with value: ' + value + ' found.';
};

LinkedList.prototype.appendToTail = function(value) {
  var newTail = new Node(value);

  // // without myList.tail property: O(n)
  // var node = this.head;
  // while(node.next) {
  //   node = node.next;
  // }
  // node.next = newTail;

  // with myList.tail property: O(1)
  this.tail.next = newTail;
  this.tail = newTail;

  return newTail;
};

LinkedList.prototype.reverseLinkedList = function () {

  // Empty or a single element Linked List
  if (!this.head || !this.head.next) {
    console.log('No duplicates were found. Empty or a single element Linked List.');
    return;
  }

  var p1 = null;
  var p2 = this.head;
  var p3;

  while (p2) {
    p3 = p2.next;
    p2.next = p1;
    p1 = p2;
    p2 = p3;
  }

  this.head = p1;
}


var isPalindrome = new LinkedList('m');
isPalindrome.appendToTail('a');
isPalindrome.appendToTail('d');
isPalindrome.appendToTail('a');
isPalindrome.appendToTail('m');
isPalindrome.appendToTail('i');
isPalindrome.appendToTail('m');
isPalindrome.appendToTail('a');
isPalindrome.appendToTail('d');
isPalindrome.appendToTail('a');
isPalindrome.appendToTail('m');

var isNotPalindrome = new LinkedList('m');
isNotPalindrome.appendToTail('a');
isNotPalindrome.appendToTail('d');
isNotPalindrome.appendToTail('a');
isNotPalindrome.appendToTail('m');
isNotPalindrome.appendToTail('i');
isNotPalindrome.appendToTail('m');
isNotPalindrome.appendToTail('m');
isNotPalindrome.appendToTail('a');
isNotPalindrome.appendToTail('d');
isNotPalindrome.appendToTail('m');
isNotPalindrome.appendToTail('a');
isNotPalindrome.appendToTail('x');

For example:

• palindrome(isPalindrome) -> true
• palindrome(isNotPalindrome) -> false

See http://js-algorithms.tutorialhorizon.com/2015/10/11/given-a-singly-linked-list-find-if-it-is-palindrome/ for additional guidance.