Check If Linked List is Palindrome in JavaScript

Question

I have written the following function in JavaScript to check if a singly Linked List is a palindrome. However, I'm failing 2 out of 10 tests, and I can't figure out why.

Here are the tests I'm falling.

1. l: [0, 1, 0]
2. l: [1, 1000000000, -1000000000, -1000000000, 1000000000, 1]

Both should return true for the palindrome, but my function is returning false.

Here's my code:

    function isListPalindrome(l) {
    let curr = l;
    let arr = [];
    
    if (l == null)
        return true;
    
    // push all elements of l into the stack.
    // a stack in JS is an array.
    while(curr != null){
        arr.push(l.value);
        
        // move ahead:
        curr = curr.next;
    }
    
    let curr2 = l;
    // Traverse the list again & check by popping from the stack:
    while(curr2 != null){
        
        // get the top most element on the stack:
        let num = arr.shift();
        
        // check if the node data isn't the same as the element popped:
        if (curr2.value != num){
            return false;
        }
        
        // move ahead:
        curr2 = curr2.next;
    }
    return true;
}

Thank you!

Answer 1

Inside the first while loop you're pushing l.value but l is not being incremented so it's pushing the same value to arr.

You now have arr which is suppose to be l in reverse. In the second while loop, instead of using arr.shift() use arr.pop(). This will take the first element off the arr stack. Remember that a stack is first in, last out.

Notice also that when you're comparing the list front to back you'll reach a point of irrelevancy, the half way point. Once you know that half the values in the forward list are the same as the values in the reverse list you know the rest will pass the test.

Here's what it's suppose to look like. You should try to figure out how to do odds yourself.

function isListPalindrome(l) {
  let curr = l;
  let arr = [];

  if (l == null)
      return true;

  // push all elements of l into the stack.
  // a stack in JS is an array.
  while(curr != null){
    arr.push(curr.value);

    // move ahead:
    curr = curr.next;
  }

  let curr2 = l;
  let length = arr.length;
  // Traverse the list again & check by popping from the stack:
  while(curr2 != null){

    // get the top most element on the stack:
    let lastNum = arr.pop();

    // check if the node data isn't the same as the element popped:
    if (curr2.value != lastNum){
      return false;
    }

    // Half way point for evens
    if (length / 2 === arr.length) {
      return true;
    }

    // move ahead:
    curr2 = curr2.next;
  }
  return true;
}

Answer 2

class Node {
    constructor(value, next = null) {
        this.value = value;
        this.next = next;
    }
}


const is_palindromic_linked_list = function (head) {

    let front = head;

    const traverse = (node) => {
        if (!node) return true;
        //reverse the LL
        const reverse = traverse(node.next);
        //check value if they are equal
        const valChecker = front.value == node.value;
        front = front.next;
        return reverse && valChecker;
    }

    return traverse(head)
};



head = new Node(2)
head.next = new Node(4)
head.next.next = new Node(6)
head.next.next.next = new Node(4)
head.next.next.next.next = new Node(2)

console.log(`Is palindrome: ${is_palindromic_linked_list(head)}`)

head.next.next.next.next.next = new Node(2)
console.log(`Is palindrome: ${is_palindromic_linked_list(head)}`)

Answer 3

I push all the elements of the list in an array and then I convert the array with join function to a string so that i can compare if the string is the same as the inverse using reverse function if it is then it is a palindrome

function isListPalindrome(l) {
  if(l === null) return true;
  let array =[];
  let current = l;
  while (current != null){
    array.push(current.value);
    current = current.next
  }
  if(array.join('')=== array.reverse().join('')) return true; 
  return false
}

Answer 4

solving with pushing values to an array and then check if the array is palindromic will have S:O(N). with reversing the second half and then traversing will have S:O(1). T:O(N) is same for both:

var isPalindrome = function (head) {
  let fast_pointer = head;
  let slow_pointer = head;
  // when fast_ppointer reaches to the tail, slow_pointer will be in the middle
  while (fast_pointer && fast_pointer.next) {
    fast_pointer = fast_pointer.next.next;
    slow_pointer = slow_pointer.next;
  }
  // now, slow_pointer is in the middle and we reverse from slow_pointer till the head
  let prev = null;
  while (slow_pointer) {
    // slow_pointer=slow_pointer.next how we iterate in linked lists.
    // so make sure we keep a reference to the next iteration
    temp = slow_pointer.next;
    slow_pointer.next = prev;
    prev = slow_pointer;
    slow_pointer = temp;
  }
  let left = head;
  let right = prev;
  while (right) {
    if (left.val !== right.val) {
      return false;
    }
    left = left.next;
    right = right.next;
  }
  return true;
};

Answer 5

var isPalindrome = function (head) {
    let values = [];
    while (head) {
        values.push(head.val);
        head = head.next;
    }
    let rev = [];
    head.map((e) => {
        rev.unshift(e);
    });
    if (values.every((val, index) => val === rev[index])) {
        return true;
    } else {
        return false;
    }
};