isPalindromeWithStack<T> function

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

Checks if a linked list is a palindrome using stack approach

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(n) due to stack usage

Implementation

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

  // Find the length of the list
  int length = 0;
  LinkedListNode<T>? current = head;
  while (current != null) {
    length++;
    current = current.next;
  }

  // Push first half to stack
  List<T> stack = [];
  current = head;
  for (int i = 0; i < length ~/ 2; i++) {
    stack.add(current!.value);
    current = current.next;
  }

  // Skip middle node if odd length
  if (length % 2 == 1) {
    current = current!.next;
  }

  // Compare with second half
  while (current != null) {
    if (stack.isEmpty || stack.removeLast() != current.value) {
      return false;
    }
    current = current.next;
  }

  return stack.isEmpty;
}