C++ iterative bottom-up merge sort, 46ms beats 94.26%


  • 0
    Y

    Inspired by the SGI STL implementation of std::list::sort (which is also used in g++ and clang as well I believe). Keep an array to maintain list with different length. Every iteration grab one node from the remained list and merge it up the ladder.

    class Solution {
    public:
        ListNode* sortList(ListNode* head) {
            ListNode* ladder[14] = {nullptr, nullptr, nullptr, nullptr, nullptr,
            nullptr, nullptr, nullptr, nullptr, nullptr,
            nullptr, nullptr, nullptr, nullptr};
            ListNode* current = nullptr;
            int fill = 0;
            while (head) {
                current = head;
                head = head->next;
                current->next = nullptr;
                int i = 0;
                for (; i < fill && ladder[i]; ++i) {
                    current = merge(current, ladder[i]);
                    ladder[i] = nullptr;
                }
                ladder[i] = current;
                if (i == fill)  ++fill;
            }
            current = nullptr;
            for (int i = 0; i < fill; ++i) {
                current = merge(current, ladder[i]);
            }
            return current;
        }
        
        ListNode* merge(ListNode* a, ListNode* b) {
            if (!a) return b;
            ListNode dummy(0);
            auto current = &dummy;
            while (a && b) {
                if (a->val < b->val) {
                    current->next = a;
                    a = a->next;
                }
                else {
                    current->next = b;
                    b = b->next;
                }
                current = current->next;
            } 
            if (a)  current->next = a;
            if (b)  current->next = b;
            return dummy.next;
        }
    };
    
    
    
    

Log in to reply
 

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