reverseBetween<T> function

LinkedListNode<T>? reverseBetween<T>(LinkedListNode<T>? head, int left, int right)

Reverses the nodes between two positions (inclusive)

head - The head of the linked list left - The left position (1-indexed) right - The right position (1-indexed) Returns the new head of the linked list

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

Implementation

LinkedListNode<T>? reverseBetween<T>(
  LinkedListNode<T>? head,
  int left,
  int right,
) {
  if (head == null || left == right) return head;

  // Create a dummy node to handle edge cases
  LinkedListNode<T> dummy = LinkedListNode<T>(head.value);
  dummy.next = head;
  LinkedListNode<T>? prev = dummy;

  // Move to the node before the left position
  for (int i = 0; i < left - 1; i++) {
    prev = prev!.next;
  }

  // Start reversing from the left position
  LinkedListNode<T>? current = prev!.next;
  for (int i = 0; i < right - left; i++) {
    LinkedListNode<T>? next = current!.next;
    current.next = next!.next;
    next.next = prev.next;
    prev.next = next;
  }

  return dummy.next;
}