class Solution {

public:

    TreeNode *sortedListToBST(ListNode *head) {

        if (!head) return nullptr;

        return sortedListToBST(head, nullptr);

    }

    TreeNode *sortedListToBST(ListNode* head, ListNode* tail) {

        if (head == tail) return nullptr;

        ListNode* mid = head, *tmp = head;

        while (tmp != tail && tmp->next != tail) {

            mid = mid->next;

            tmp = tmp->next->next;

        }

        TreeNode* root = new TreeNode(mid->val);

        root->left = sortedListToBST(head, mid);

        root->right = sortedListToBST(mid->next, tail);

        return root;

    }

};

class Solution {

public:

    TreeNode* sortedListToBST(ListNode* head) {

        if (head == nullptr)

            return nullptr;

        ListNode* fast = head;

        ListNode* slow = head;

        ListNode* prev = nullptr;

        while (fast != nullptr && fast->next != nullptr)

        {

            fast = fast->next->next;

            prev =slow;

            slow = slow->next;

        }

        TreeNode* root = new TreeNode(slow->val);

        if (prev != nullptr)

            prev->next = nullptr;

        else

            head  = nullptr;

        root->left = sortedListToBST(head);

        root->right = sortedListToBST(slow->next);

        return root;

    }

};