Share my nlogn solution and keeping the original link list


  • 0
    T
    TreeNode* helper(ListNode* h, int len){
        TreeNode* root = NULL;
        if(len == 0){
            return root;
        }else{
            int tmp = 1;
            while(tmp*2-1 <= len){
                tmp*=2;
            }
            int noLe = (tmp-1)/2 + min((len-(tmp-1)), tmp/2);
            int noRi = len - 1 - noLe;
            int j = noLe;
            ListNode* node = h;
            while(node && j >0){
                j--;
                node = node->next;
            }
            root = new TreeNode(node->val);
            root->left = helper(h, noLe);
            root->right = helper(node->next, noRi);
            return root;
        }
    }
    
    TreeNode* sortedListToBST(ListNode* head) {
            
        ListNode* node = head;
        TreeNode *root = NULL;
        int len = 0;
        while(node){
            node = node->next;
            len++;
        }
        
        root = helper(head, len);
        return root;
    }
    

    };


Log in to reply
 

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