Convert a doubly linked list to a binary search tree in place. Think… Suppose the input list is 3 2 1 6 4 7 This is the way to convert sorted linked l

Convert a doubly linked list to a binary search tree in place. Think…
Suppose the input list is 3 2 1 6 4 7
list* foo(list* head)
{
if(!head) return NULL;
list* head1=head2=NULL;
findNewHead(head,head1,head2);
head->left=foo(head1);
head->right=foo(head2);
return head;
}

findNewHead(list* head, list*& head1, list*& head2)
{
if(!head->next) return;
if(head->val>head->next->val)
head1=head->next;
while(head->next)
{
if(head->val>head->next->val)
head=head->next;
else
{
head2=head->next;
head ->next=NULL;
head2->prev=NULL;
return;
}
}
return;
}