class Solution {
public:
TreeNode *sortedListToBST(ListNode *head)
{
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;
}
};
My Accepted C++ solution


Good solution, but we can do better. Following shorter solution runs 22ms:
TreeNode* sortedListToBST(ListNode* head) { if (!head) return nullptr; if (!head>next) return new TreeNode(head>val); 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>left = sortedListToBST(head); root>right = sortedListToBST(mid>next); return root; }


@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. =_=
