C++ Solution in Merge Sort 53s


  • 0
    T
    
        ListNode* Merge(ListNode* left, ListNode* right)
        {
            ListNode* root = new ListNode(0);
            ListNode* node = root;
    
            while(left != NULL && right != NULL)
            {
                if(left->val < right->val)
                {
                    node->next = left;
                    left = left->next;
                }
                else
                {
                    node->next = right;
                    right = right->next;
                }
    
                node = node->next;
            }
    
            if(left == NULL)
                node->next = right;
    
            if(right == NULL)
                node->next = left;
    
            node = root;
            root = root->next;
            node->next = NULL;
            delete node;
    
            return root;
        }
    
        ListNode* sortList(ListNode* root)
        {
            if(root == NULL || root->next == NULL)
                return root;
    
            ListNode* quick = root->next;
            ListNode* slow = root;
    
            while(quick != NULL && quick->next != NULL)
            {
                quick = quick->next->next;
                slow = slow->next;
            }
    
            ListNode* mid = slow->next;
            slow->next = NULL;
    
            root = sortList(root);
            mid = sortList(mid);
    
            return Merge(root, mid);
        }
    
    

Log in to reply
 

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