Implement a function to check if a linked list is a palindrome

Linked lists are fundamental data structures, and understanding their properties is important for any programmer. One interesting problem is determining if a given linked list is a palindrome – meaning it reads the same forwards and backward. This blog post will walk you through implementing a JavaScript function to efficiently solve this problem.

We’ll first define a Node class to represent elements within our linked list:

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

Next, we need a function to create a linked list from an array:

function createLinkedList(arr) {
  let head = null;
  let tail = null;
  for (let i = 0; i < arr.length; i++) {
    const node = new Node(arr[i]);
    if (head === null) {
      head = node;
      tail = node;
    } else {
      tail.next = node;
      tail = node;
    }
  }
  return head;
}

Now, let’s get to the core function: checking if the linked list is a palindrome. We’ll employ a common technique involving reversing the second half of the list and comparing it to the first half. This approach ensures an efficient O(n) time complexity solution.

function isLinkedListPalindrome(head) {
  //Handle empty or single-node lists
  if (head === null || head.next === null) return true;

  //Find the middle of the linked list using slow and fast pointers
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }

  //Reverse the second half of the linked list
  let secondHalfHead = reverseLinkedList(slow);

  //Compare the first and reversed second halves
  let firstHalf = head;
  let secondHalf = secondHalfHead;
  while (secondHalf !== null) {
    if (firstHalf.data !== secondHalf.data) {
      return false;
    }
    firstHalf = firstHalf.next;
    secondHalf = secondHalf.next;
  }

  return true;
}


//Helper function to reverse a linked list
function reverseLinkedList(head) {
  let prev = null;
  let curr = head;
  while (curr !== null) {
    let nextTemp = curr.next;
    curr.next = prev;
    prev = curr;
    curr = nextTemp;
  }
  return prev;
}

Let’s test our function:

const list1 = createLinkedList([1, 2, 3, 2, 1]);
const list2 = createLinkedList([1, 2, 3, 4, 5]);
const list3 = createLinkedList([1,2,1]);
const list4 = createLinkedList([]);
const list5 = createLinkedList([5]);

console.log(isLinkedListPalindrome(list1)); // true
console.log(isLinkedListPalindrome(list2)); // false
console.log(isLinkedListPalindrome(list3)); // true
console.log(isLinkedListPalindrome(list4)); // true
console.log(isLinkedListPalindrome(list5)); // true

This code effectively demonstrates how to determine if a linked list forms a palindrome in JavaScript. The use of slow and fast pointers for finding the middle and the helper function for reversing the linked list contributes to a clean and efficient solution. Remember to handle edge cases such as empty or single-node lists for a complete implementation.