reverseDoublyLinkedList<T> function

DoublyLinkedListNode<T>? reverseDoublyLinkedList<T>(DoublyLinkedListNode<T>? head)

Reverses a doubly linked list

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

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

Implementation

DoublyLinkedListNode<T>? reverseDoublyLinkedList<T>(
  DoublyLinkedListNode<T>? head,
) {
  DoublyLinkedListNode<T>? current = head;
  DoublyLinkedListNode<T>? temp;

  // Traverse the list and swap next and prev pointers
  while (current != null) {
    // Store the next node
    temp = current.next;

    // Swap next and prev pointers
    current.next = current.prev;
    current.prev = temp;

    // Move to the next node (which is now in prev due to swap)
    current = temp;
  }

  // Return the new head (last node of original list)
  return temp?.prev ?? head;
}