isPalindrome<T> function

bool isPalindrome<T>(LinkedListNode<T>? head)

Checks if a linked list is a palindrome

head - The head of the linked list to check Returns true if the linked list is a palindrome, false otherwise

Time Complexity: O(n) where n is the length of the list Space Complexity: O(1)

Implementation

bool isPalindrome<T>(LinkedListNode<T>? head) {
  if (head == null || head.next == null) return true;

  // Find the middle of the list
  LinkedListNode<T>? slow = head;
  LinkedListNode<T>? fast = head;

  while (fast!.next != null && fast.next!.next != null) {
    slow = slow!.next;
    fast = fast.next!.next;
  }

  // Reverse the second half
  LinkedListNode<T>? secondHalf = reverseLinkedList(slow!.next);
  LinkedListNode<T>? firstHalf = head;

  // Compare the two halves
  LinkedListNode<T>? temp = secondHalf;
  bool result = true;

  while (secondHalf != null) {
    if (firstHalf!.value != secondHalf.value) {
      result = false;
      break;
    }
    firstHalf = firstHalf.next;
    secondHalf = secondHalf.next;
  }

  // Restore the original list
  slow.next = reverseLinkedList(temp);

  return result;
}