Divide & Conquer C++ Solution


  • 0
    M

    The algorithm is straightforward. The trick is how to handle the median ListNode.
    First, get the length of the list, then there are (length -1)/2 nodes between median and head.
    The left side length of the median is (length-1)/2, the right side length of the median is length/2.
    Then everything is very easy.

    ListNode *getMid(ListNode *head, int length) {
        int steps = (length-1)/2; // (length-1) is very important, can handle both the even&odd cases
        while(steps--) head = head->next;
        return head;
    }
    TreeNode *convert(ListNode *head, int length) {
        if (head == nullptr || length == 0) return {nullptr};
    
        ListNode *median = getMid(head, length);
        TreeNode * root = new TreeNode(median->val);
        root->left = convert(head,(length-1)/2); // Be careful here ! if u can't make it, take examples to help!
        root->right = convert(median->next,length/2);
        return root;
    }
    TreeNode *sortedListToBST(ListNode *head) {
        int length = 0;
        ListNode *p = head;
        while (p != nullptr) {p = p->next; length++;}
        return convert(head, length);
    }

Log in to reply
 

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