Palindrome Linked List

Given the head of a linked list, your task is to check whether the linked list is a palindrome or not. Return TRUE if the linked list is a palindrome; otherwise, return FALSE.

Given the head of a linked list, your task is to check whether the linked list is a palindrome or not. Return TRUE if the linked list is a palindrome; otherwise, return FALSE.

Note

The input linked list prior to the checking process should be identical to the list after the checking process has been completed.

Constraints

Let n be the number of nodes in a linked list.

• 1 ≤ n ≤ 500
• 0 ≤ Node.value ≤ 9

Solution

We'll need to find middle of linkedlist using fast and slow pointer then reverse linked list and compare. To reverse a linked list we save next element and point current then we move forward by making prev to current and current to next.

function reverseLinkedList(head){
let prev= null;
let curr=head;
let next=head.next;

while(curr!==null){

let next = curr.next
curr.next= prev;
prev=curr;
curr=next;

}

return prev;
}

// Check palindrome in linkedList
function palindrome(head) {
  // Initialize slow and fast pointers to the head of the linked list
  var fast, slow;
  slow = head;
  fast = head;

  // Find the middle of the linked list using the slow and fast pointers
  while (fast && fast.next) {
    // move slow one step forward
    slow = slow.next;
    // move fast two steps forward
    fast = fast.next.next;
  }

  // Reverse the second half of the linked list starting from the middle node
  revertData = reverseLinkedList(slow);

  // Compare the first half of the linked list with the reversed second half of the linked list

  var check = compareTwoHalves(head, revertData);

  // Re-reverse the second half of the linked list to restore the original linked list
  reverseLinkedList(revertData);

  // Return True if the linked list is a palindrome, else False
  if (check) {
    return true;
  }

  return false;
}

function compareTwoHalves(firstHalf, secondHalf) {
  // Compare the corresponding nodes of the first and second halves of the linked list
  while (firstHalf !== null && secondHalf !== null) {
    if (firstHalf.data !== secondHalf.data) {
      return false;
    } else {
      firstHalf = firstHalf.next;
      secondHalf = secondHalf.next;
    }
  }
  return true;
}