Преобразовать связанный список в двоичное дерево поиска?

Question

Имея круговой двусвязный список ... Как я могу преобразовать его в дерево бинарного поиска ..

Вопрос найден на http://rajeevprasanna.blogspot.com/2011/02/convert-binary-tree-into-doubly-linked.html

Я пытался написать код для того же, но он задохнулся! Пожалуйста, некоторые предложения здесь будут хорошими. Кроме того, как я могу найти середину связанного списка .. Пожалуйста, говорите с точки зрения кода (код C или C ++), и, если возможно, небольшой пример был бы хорош в остальном.

Просматривая статью (URL), которую я предоставил выше, BST to Linked List был хорошим упражнением. Я пытался следовать тому же принципу, но моя программа задохнулась ... Пожалуйста, помогите ...

Node ListToTree(Node head)
{
    if(head == NULL)
        return NULL;

    Node hleft = NULL, hright = NULL;

    Node root = head;

    hleft = ListToTree(head->left);
    head->left = NULL;
    root->left = hleft;

    hright = ListToTree(head->right);
    head->right = NULL;
    root->right = hright;

    return root;
}

Answer 1

class Node {
  Node *prev, *next;
  int value;
}

void listToTree(Node * head) {
    if (head == null)
        return;
    if (head->next == head) {
        head->prev = null;
        head->next = null;
        return head;
    }
    if (head->next->next == head) {
        head->prev = null;
        head->next->next = null;
        head->next->prev = null;
        return head;
    }

    Node *p1 = head, *p2 = head->prev;
    while (p1->value < p2.value)
        p1 = p1->next, p2 = p2->prev;
    Node * root = p1;
    root->prev->next = head;
    root->next->prev = head->prev;
    root->prev = listToTree(head);
    root->next = listToTree(root->next);
    return root;
}