Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Solution:
TreeNode *sortedListToBST(ListNode *head) {
if(head == NULL)
return NULL;
if(head->next == NULL)
return new TreeNode(head->val);
ListNode * current = head;
int size = ;
while(current != NULL){
size ++;
current = current->next;
}
current = head;
int median = size / ;
int count = ;
ListNode * median_node = NULL;
ListNode * pre_node = NULL;
while(current != NULL){
if(count == median){
median_node = current;
pre_node->next = NULL;
break;
}
count ++;
pre_node = current;
current = current->next;
}
TreeNode * root = new TreeNode(median_node->val);
root->left = sortedListToBST(head);
root->right = sortedListToBST(median_node->next);
return root;
}