Conversión en el lugar de DLL ordenada a BST balanceada

Dada una lista doblemente enlazada que tiene miembros de datos ordenados en orden ascendente. Construya un árbol de búsqueda binario equilibrado que tenga los mismos miembros de datos que la lista doblemente enlazada dada. El árbol debe construirse en el lugar (no se debe asignar ningún Node nuevo para la conversión del árbol) 

Ejemplos: 

Input:  Doubly Linked List 1  2  3
Output: A Balanced BST 
     2   
   /  \  
  1    3 


Input: Doubly Linked List 1  2 3  4 5  6  7
Output: A Balanced BST
        4
      /   \
     2     6
   /  \   / \
  1   3  5   7  

Input: Doubly Linked List 1  2  3  4
Output: A Balanced BST
      3   
    /  \  
   2    4 
 / 
1

Input:  Doubly Linked List 1  2  3  4  5  6
Output: A Balanced BST
      4   
    /   \  
   2     6 
 /  \   / 
1   3  5   

La conversión de la lista doblemente enlazada es muy similar a este problema de la lista enlazada individualmente y el método 1 es exactamente el mismo que el método 1 de la publicación anterior . El método 2 también es casi el mismo. La única diferencia en el método 2 es que, en lugar de asignar nuevos Nodes para BST, reutilizamos los mismos Nodes DLL. Usamos el puntero anterior como izquierdo y el siguiente como derecho.

Método 1 (Simple) El 
siguiente es un algoritmo simple en el que primero encontramos el Node medio de la lista y lo convertimos en la raíz del árbol que se va a construir.  

1) Get the Middle of the linked list and make it root.
2) Recursively do same for left half and right half.
       a) Get the middle of left half and make it left child of the root
          created in step 1.
       b) Get the middle of right half and make it right child of the
          root created in step 1.

Complejidad de tiempo: O(nLogn) donde n es el número de Nodes en la lista enlazada.

Método 2 (complicado) 
El método 1 construye el árbol desde la raíz hasta las hojas. En este método, construimos desde las hojas hasta la raíz. La idea es insertar Nodes en BST en el mismo orden en que aparecen en la Lista doblemente enlazada, de modo que el árbol pueda construirse en una complejidad de tiempo O(n). Primero contamos el número de Nodes en la lista enlazada dada. Sea la cuenta n. Después de contar los Nodes, tomamos n/2 Nodes a la izquierda y construimos recursivamente el subárbol izquierdo. Después de construir el subárbol izquierdo, asignamos el Node medio a la raíz y vinculamos el subárbol izquierdo con la raíz. Finalmente, construimos recursivamente el subárbol derecho y lo vinculamos con la raíz. 
Mientras construimos el BST, también seguimos moviendo el puntero del encabezado de la lista al siguiente para que tengamos el puntero apropiado en cada llamada recursiva. 

A continuación se muestra la implementación del método 2. El código principal que crea Balanced BST está resaltado.