有序链表转换二叉搜索树

 1TreeNode* sortedListToBST(ListNode* head)
 2{
 3    if(head == nullptr) return nullptr;
 4    if(head->next == nullptr) return new TreeNode(head->val);
 5
 6    // 找出链表的中点
 7    // 循环结束时，slow 即为树的根节点
 8    // 同时 slow 左边的链表为左子树，slow 右边为右子树
 9    ListNode *slow = head, *fast = head, *prev = nullptr;
10    while(fast != nullptr && fast->next != nullptr)
11    {
12        prev = slow;
13        slow = slow->next;
14        fast = fast->next->next;
15    }
16
17    prev->next = nullptr;
18    TreeNode* root = new TreeNode(slow->val);
19    root->left = sortedListToBST(head);
20    root->right = sortedListToBST(slow->next);
21    return root;
22}