Palindrome linked list

Easy TimeO(n) SpaceO(n)

Given the head of a singly linked list, return true when its values read the same forwards and backwards — [1, 2, 3, 2, 1] does. The list can only be traversed forwards, comparison is by value rather than by node, and an empty list or a single node is a palindrome.

Examples

Example 1

Input
head = buildList([1, 2, 3, 2, 1])
Output
true
1 and 1, 2 and 2, with the 3 alone in the middle.

Example 2

Input
head = buildList([1, 2])
Output
false
1 and 2 are different values, so it does not read the same backwards.

The Code

function buildList(values) {
  let head = null;
  for (let i = values.length - 1; i >= 0; i--) {
    head = { val: values[i], next: head };
  }
  return head;
}
function isPalindrome(head) {
  const values = [];
  let node = head;
  while (node) {
    values.push(node.val);
    node = node.next;
  }
  let left = 0;
  let right = values.length - 1;
  while (left < right) {
    if (values[left] !== values[right]) return false;
    left++;
    right--;
  }
  return true;
}
isPalindrome(buildList([1, 2, 3, 2, 1]));
Done

The first 9 calls, of 17. This one does not fit on a page.

Step through isPalindrome(buildList([1, 2, 3, 2, 1])) call by call

More like this

All linked lists examples (9) →