C++ Easy to understand, clean code, split list into halves and merge


  • 0
    W
    ListNode* sortBinary(ListNode* head, int size)
    {
        if (size <= 1) return head;
        
        int half = size / 2;
        auto node = head;
        for (int i = 1; i < half; i++)
            node = node->next;
        
        auto nextHalf = node->next;
        node->next = nullptr;
        auto leftNode = sortBinary(head, half);
        auto rightNode = sortBinary(nextHalf, size - half);
        
        if (leftNode->val <= rightNode->val)
        {
            head = leftNode;
            leftNode = leftNode->next;
        }
        else
        {
            head = rightNode;
            rightNode = rightNode->next;
        }
        
        auto end = head;
        while (leftNode && rightNode)
        {
            if (leftNode->val <= rightNode->val)
            {
                end->next = leftNode;
                leftNode = leftNode->next;
            }
            else
            {
                end->next = rightNode;
                rightNode = rightNode->next;
            }
            end = end->next;
        }
        
        while (leftNode)
        {
            end->next = leftNode;
            leftNode = leftNode->next;
            end = end->next;
        }
        
        while (rightNode)
        {
            end->next = rightNode;
            rightNode = rightNode->next;
            end = end->next;
        }
        
        return head;
    }
    
    ListNode* sortList(ListNode* head) 
    {
        auto node = head;
        int size = 0;
        while (node)
        {
            size++;
            node = node->next;
        }
        
        return sortBinary(head, size);
    }

Log in to reply
 

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