Convert a Sorted Doubly Linked List to a Balanced BST In Place

Problem Statement

Given the head of a sorted doubly linked list, convert it into a height-balanced Binary Search Tree (BST) in place without allocating any new nodes.

In the resulting BST:

• The prev pointer of each node should represent its left child.
• The next pointer of each node should represent its right child.
• A height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than 1.

Return the root node of the constructed BST.

Node Definition

class DLNode:
    def __init__(self, val=0, prev=None, next=None):
        self.val = val
        self.prev = prev  # acts as left child in BST
        self.next = next  # acts as right child in BST

Function Signature

def sorted_dll_to_bst(head: Optional[DLNode]) -> Optional[DLNode]:
    pass

Examples

Example 1:

Input: head = 1  2  3  4  5  6  7
Output: [4, 2, 6, 1, 3, 5, 7]
Explanation:
One valid balanced BST representation:
        4
      /   \
     2     6
    / \   / \
   1   3 5   7
Node pointers are rewired such that 4.prev = 2, 4.next = 6, etc.

Example 2:

Input: head = -10  -3  0  5  9
Output: [0, -3, 9, -10, null, 5]
Explanation:
        0
      /   \
    -3     9
    /     /
  -10    5
Both subtrees of each node differ in depth by at most 1.

Constraints

• The number of nodes in the linked list is in the range [0, 10^5].
• -10^9 <= DLNode.val <= 10^9
• The doubly linked list is sorted in non-decreasing order.
• You must achieve O(N) time complexity and O(log N) auxiliary stack space.
• No new DLNode instances may be created.

Edge Cases

• Empty list (head = None): Return None.
• Single node list: The node itself is returned with prev = None and next = None.
• Even number of nodes: Either valid median may serve as the root as long as the balanced property is maintained.