My c++ solution, use fast slow pointer


  • 0
    L

    public:
    TreeNode* sortedListToBST(ListNode* head) {
    if(!head) return NULL;

        TreeNode * root = helper(head, NULL);
        return root;
    }
    
    ListNode* mid(ListNode *start, ListNode *end) {
        if (!start || start == end) return NULL;
        ListNode* fast = start;
        ListNode* slow = start;
        while(fast->next != end && fast->next->next != end) {
            fast = fast->next->next;
            slow = slow->next;
        }
        
        return slow;
    }
    
    TreeNode* helper(ListNode *start, ListNode *end){
         if (!start|| start == end) return NULL;
         ListNode *p = mid(start, end);
         TreeNode * root = new TreeNode(p->val);
         root->left = helper(start, p);
         root->right = helper(p->next, end);
         return root;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.