C++ O(1) space merge sort (non-recursive, constant stack space usage)


  • 0
    class Solution {
    public:
        // Cut the first n items of list p to form a new list
        // Return the pointer to the following item (the= (n+1)th item) in p
        ListNode* cutN(ListNode *p, int n) {
            ListNode *last = nullptr;
            while(n && p) {
                last = p;
                p = p->next;
                n --;
            }
            if (last)
                last->next = nullptr;
            return p;
        }
    
        // Merge list a and list b
        // Return pointers to the first and the last item in the merged list
        pair<ListNode*, ListNode*> merge(ListNode *a, ListNode *b) {
            ListNode *first = nullptr;
            ListNode *last = nullptr;
            
            while (a || b) {
                ListNode *next = nullptr;
                if (a && (!b || a->val < b->val)) {
                    next = a;
                    a = a->next;
                } else {
                    next = b;
                    b = b->next;
                }
                if (!first) first = next;
                if (last) last->next = next;
                last = next;
            }
            return {first, last};
        }
        
        ListNode* sortList(ListNode* head) {
            // Count the total number of nodes
            int n=0;
            ListNode* p = head;
            while (p) {
                n ++;
                p = p->next;
            }
            
            // Before each iteration, every s items in the list is already sorted,
            // the list contains n/s sorted runs.
            // In each iteration, every 2 adjacent sorted runs are merged into a 2s-item sorted run
            // This loop is executed log(2, n) times
            for (int s=1; s<n; s<<=1) {
                ListNode *a, *b;
                ListNode *next = head;
                ListNode **last = &head;
                
                // This loop is executed n/s times
                while (next) {
                    // cutN() takes O(s) time
                    a = next;
                    b = cutN(next, s);
                    next = cutN(b, s);
    
                    // Merge() takes O(s) time
                    auto p = merge(a, b);
                    (*last) = p.first;
                    p.second->next = next;
                    last = &(p.second->next);
                }
            }
            
            return head;
        }
    };
    
    

Log in to reply
 

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