通过有序链表构建平衡二叉搜索树

思路和数组差不多，只是链表需要通过快慢指针找到中间节点：

• 根据题目示例，如果节点个数为偶数个，应该将中间偏右的那个作为根节点；
• 不需要断链，如果断链反而麻烦很多。

总结一下如何定位中间偏右（偶数个节点数）的节点以及如何定位中间偏左的节点：

• 中间偏右：循环条件为!fast && !fast->next
• 中间偏左：循环条件为!fast->next && !fast->next->next
• (本题需要根据上面略微修改一下)

代码如下：

class Solution {
public:
    /**
     *
     * @param head ListNode类
     * @return TreeNode类
     */
    TreeNode* sortedListToBST(ListNode* head) {
        // write code here
        return preOrder(head, nullptr);
    }

    TreeNode* preOrder(ListNode* head, ListNode *end) {
        // 快慢指针找中点
        if (head == end) return nullptr;
        ListNode *fast = head, *slow = head;
        while (fast != end && fast->next != end) {
            fast = fast->next->next;
            slow = slow->next;
        }
        TreeNode *root = new TreeNode(slow->val);
        // 构建左右
        root->left = preOrder(head, slow);
        root->right = preOrder(slow->next, end);
        return root;
    }
};