My Accepted C++ Solution Without Destroying the Original List


  • 0
    O

    The idea is from other people and I used "start" and "end" node to prevent from destroying the list.

    TreeNode *helper(ListNode* start, ListNode* end) {
            //end is the node out of the search boundary
            if (start == end) {
                return NULL;
            }
            ListNode *slow = start;
            ListNode *fast = start;
            while (fast != end && fast->next != end) {
                slow = slow->next;
                fast = fast->next->next;
            }
            TreeNode *root = new TreeNode(slow->val);
            root->left = helper(start, slow);
            root->right = helper(slow->next, end);
            
            return root;
        }
    
        TreeNode* sortedListToBST(ListNode* head) {
            if (!head) {
                return NULL;
            }
            if (!head->next) {
                return new TreeNode(head->val);
            }
            
            return helper(head, NULL);
            
        }
    

Log in to reply
 

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