TreeNode *sortedListToBST(ListNode *head) {
if(head == NULL) return NULL;
if(head>next == NULL) return new TreeNode(head>val);
ListNode *step1 = head;
ListNode *step2 = head>next;
while(step2>next != NULL && step2>next>next != NULL){
step1 = step1>next;
step2 = step2>next>next;
}
TreeNode *root = new TreeNode(step1>next>val);
ListNode *head2 = step1>next>next;
delete step1>next;
step1>next = NULL;
root>left = sortedListToBST(head);
root>right = sortedListToBST(head2);
return root;
}
Sorted List to binary search tree O(nlogn) time complexity


Do bottom up approach and construct the tree from the leaves rather than doing top down approach and constructing tree from root to get o(n) time complexity.
STEP 1: Take left n/2 nodes and recursively construct the left sub tree.
STEP 2: After left sub tree is constructed, we allocate memory for root and link the left sub tree with root.
STEP 3: Finally, we recursively construct the right sub tree and link it with root.
class Solution { public: ListNode *list; int lengthOfList(ListNode *node){ int length = 0; while (node) { length++; node = node>next; } return length; } TreeNode *populateTree(int n){ if (n == 0) return NULL; TreeNode *treenode = new TreeNode(0); treenode>left = populateTree(n / 2); treenode>val = list>val; list = list>next; treenode>right = populateTree(n  n / 2  1); return treenode; } TreeNode *sortedListToBST(ListNode *head) { this>list = head; return populateTree(lengthOfList(head)); } };

Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example