MaiDeveloper

Palindrome Linked List in JavaScript

Given the head of a singly linked list, return true if it is a palindrome.

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

Given the List Node class.

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

What is palindrome?

A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward, such as madam or racecar. There are also numeric palindromes, including date/time stamps using short digits 11/11/11 11:11 and long digits 02/02/2020. Sentence-length palindromes ignore capitalization, punctuation, and word boundaries.
Wikipedia

Solution 1

Traverse the whole linked list and store the values into a string variable; and then check whether or not the string is a palindrome.

/**
 * @param {string} st
 * @return {boolean}
 * @time complexity: O(n)
 * @space complexity: O(n)
 */
const isValidPalindrome = str => {
  let i = 0;
  let j = str.length - 1;

  while (i < j) {
    if (str[i] !== str[j]) {
      return false;
    }

    i++;
    j--;
  }

  return true;
};

/**
 * @param {ListNode} head
 * @return {boolean}
 * @time complexity: O(n)
 * @space complexity: O(n)
 */
const isPalindrome = head => {
  let str = '';

  while (head) {
    str += head.val;
    head = head.next;
  }

  return isValidPalindrome(str);
};

Solution 2

We can also write a Rrecursive function to check the values whether they are palindrome.

/**
 * @param {ListNode} head
 * @return {boolean}
 * @time complexity: O(n)
 * @space complexity: O(n)
 */
const isPalindrome2 = head => {

  const reverseCheck = node => {
    if (node !== null) {
      if (!reverseCheck(node.next)) {
        return false;
      }

      if (node.val !== head.val) {
        return false;
      }

      head = head.next;
    }

    return true;
  };

  return reverseCheck(head);
};

Test Case

const assert = require('chai').assert;

const createLinkedList = arr => {
  const dummy = new ListNode();
  let curr = dummy;

  for (const ele of arr) {
    curr.next = new ListNode(ele);
    curr = curr.next;
  }

  return dummy.next;
};


describe('Palindrome Linked List', () => {

  describe('Solution 1', () => {
    it('should return true', () => {
      const input = createLinkedList([1, 2, 2, 1]);
      const result = isPalindrome(input);
      const expected = true;

      assert.strictEqual(result, expected);
    });

    it('should return false', () => {
      const input = createLinkedList([1, 2]);
      const result = isPalindrome(input);
      const expected = false;

      assert.strictEqual(result, expected);
    });
  });

  describe('Solution 2', () => {
    it('should return true', () => {
      const input = createLinkedList([1, 2, 2, 1]);
      const result = isPalindrome2(input);
      const expected = true;

      assert.strictEqual(result, expected);
    });

    it('should return false', () => {
      const input = createLinkedList([1, 2]);
      const result = isPalindrome2(input);
      const expected = false;

      assert.strictEqual(result, expected);
    });
  });

});

  Palindrome Linked List
    Solution 1
      ✓ should return true
      ✓ should return false
    Solution 2
      ✓ should return true
      ✓ should return false


  4 passing (14ms)


Mike Mai
Mike Mai   Brooklyn, New York
I am full-stack web developer, passionate about building world class web applications. Knowledge in designing, coding, testing, and debugging. I love to solve problems.