有序链表转换二叉搜索树（快慢指针）

题目：https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/ 参考：https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/solution/c-2chong-jie-fa-bu-yong-duan-kai-lian-biao-by-alex/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    /*
    *给定有序链表，构造二叉搜索树
    *快慢指针
    */
    void dfs(TreeNode *&root,ListNode *head,ListNode *tail) {
        if(head == tail) return;
        ListNode *slow = head,*fast = head;
        while(fast != tail && fast->next != tail) {
            slow = slow->next;
            fast = fast->next->next;
        }
        root = new TreeNode(slow->val);
        dfs(root->left,head,slow);
        dfs(root->right,slow->next,tail);
    }
    TreeNode* sortedListToBST(ListNode* head) {
        TreeNode *root;
        if(head == nullptr) return nullptr;
        dfs(root,head,nullptr);
        return root;
    }
};