Convert Sorted List to Binary Search Tree

• Time : $O(nlogn)$
• Space : $O(1)$

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
ListNode* cut(ListNode* A) {
    ListNode* slow = A;
    ListNode* fast = A;
    ListNode* prev = slow;
    while(fast->next and fast->next->next) {
        prev = slow;
        slow = slow->next;
        fast = fast->next->next;
    }
    return prev;
}
TreeNode* Solution::sortedListToBST(ListNode* A) {
    if(A == NULL) return NULL;
    if(A->next == NULL) return new TreeNode(A->val);
    ListNode* now = cut(A);
    TreeNode* res = new TreeNode(now->next->val);
    ListNode* right = now->next->next;
    ListNode* left = A;
    now->next->next = NULL;
    now->next = NULL;
    res->left = sortedListToBST(left);
    if(right != NULL) res->right = sortedListToBST(right);
    return res;
}