reverseLinkedListRecursive<T> function

LinkedListNode<T>? reverseLinkedListRecursive<T>(LinkedListNode<T>? head)

Reverses a singly linked list recursively

head - The head of the linked list to reverse Returns the new head of the reversed linked list

Time Complexity: O(n) where n is the length of the list Space Complexity: O(n) due to recursion stack

Implementation

LinkedListNode<T>? reverseLinkedListRecursive<T>(LinkedListNode<T>? head) {
  // Base case: empty list or single node
  if (head == null || head.next == null) {
    return head;
  }

  // Recursively reverse the rest of the list
  LinkedListNode<T>? newHead = reverseLinkedListRecursive(head.next);

  // Reverse the link
  head.next!.next = head;
  head.next = null;

  return newHead;
}