C++ O(1) memory solution


  • 0
    J

    using slow-fast to find the mid node and cut the list into 2 list. then recursively generate the tree

    class Solution {
    public:
        TreeNode* sortedListToBST(ListNode* head) {
            if(head == NULL)
                return NULL;
            pair<ListNode*, ListNode*> myPair = findMidNode(head);
            if(myPair.second == NULL)
                return NULL;
            TreeNode* root = new TreeNode(myPair.second->val);
            ListNode* right = myPair.second->next;
            if(myPair.first == NULL)
            {
                root->left = NULL;
            }
            else
            {
                myPair.first->next = NULL;
                root->left = sortedListToBST(head);
            }
            root->right = sortedListToBST(right);
            return root;
        }
        
        pair<ListNode*, ListNode*> findMidNode(ListNode* head)
        {
            ListNode* pre=NULL;
            ListNode* slow = head;
            ListNode* fast = head;
            while(fast && fast->next)
            {
                pre = slow;
                slow = slow->next;
                fast = fast->next->next;
            }
            
            return make_pair(pre, slow);
        }
    };
    

Log in to reply
 

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