# My Accepted C++ solution

• ``````class Solution {
public:
{
return sortedListToBST( head, NULL );
}

private:
TreeNode *sortedListToBST(ListNode *head, ListNode *tail)
{
if( head == tail )
return NULL;
if( head->next == tail )    //
{
TreeNode *root = new TreeNode( head->val );
return root;
}
ListNode *mid = head, *temp = head;
while( temp != tail && temp->next != tail )    // 寻找中间节点
{
mid = mid->next;
temp = temp->next->next;
}
TreeNode *root = new TreeNode( mid->val );
root->left = sortedListToBST( head, mid );
root->right = sortedListToBST( mid->next, tail );
return root;
}
};``````

• clever way to find the middle of the list :)

when you find the mid node and using the val to construct a root TreeNode, but when you construct the left tree, why don't you delete the mid node ?

• No need. It won't be really get to the tail. Look carefully at the base case and you will know.

• adding tail param makes the program clear.
better comment it in english

• T(n) = 2T(n/2) + n
Apply the master method,O(n) = nlog(n)....

• can you tell me space and time complexity?

• can you tell me space and time complexity?

• ``````if( head->next == tail )    //
{
TreeNode *root = new TreeNode( head->val );
return root;
}
``````

this part is unecessary

• ``````if( head->next == tail )    //
{
TreeNode *root = new TreeNode( head->val );
return root;
}
``````

is unnecessary.

• This post is deleted!

• The way to find the mid point of a linked list is very enlightening.

• Great solution with the fast-slow pointer!

• Good solution, but we can do better. Following shorter solution runs 22ms:

``````TreeNode* sortedListToBST(ListNode* head) {
if (!head) return nullptr;
auto fast = head->next, slow = head;
while (fast->next && fast->next->next) {
fast = fast->next->next;
slow = slow->next;
}

auto mid = slow->next;
slow->next = nullptr;
auto root = new TreeNode(mid->val);
root->right = sortedListToBST(mid->next);
return root;
}
``````

• @wfxr 破坏了输入数据 如果在多线程环境下 可能比较危险

• This post is deleted!

• The step of finding the mid node is really amazing~

• @Jenny sorry that was a mistake. It's not my own answer but an incorrect reply after I copied the answer and tried to submit. And the most awkward thing was that because of my insufficient privilege, I was even not able to purge it. =_=

• @wfxr why the mid = slow->next?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.