cehsu
3,263 views

### Open Source Your Knowledge, Become a Contributor

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;
}

if (headValue === undefined) console.log('Must provide value for first node');
}

while (node) {
callback(node.value);
node = node.next;
}
};

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

// 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;
};

// 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;
};

};

}

while (node) {
if (node.value === value) return node;
node = node.next;
}
return 'No node with value: ' + value + ' found.';
};

var newTail = new Node(value);

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

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

return newTail;
};

// Empty or a single element Linked List
console.log('No duplicates were found. Empty or a single element Linked List.');
return;
}

var p1 = null;
var p3;

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

}

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

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