True O(1) space bottom up Merge Sort


  • 0
    Q

    As I said in another post, anything that uses recursion is O(log N) space complexity.
    Here is my bottom up iterative merge sort solution. Took me a lot of time to compress it to under 50 lines.
    It will be much harder to implement/debug if we don't count the length of the list first, so bear with me.
    Also it is very hard to debug if we don't take up the next two sub-list out of the original list and NULL their ends.

    class Solution {
    public:
        ListNode* sortList(ListNode* head) {
            if(!head || !head->next) return head;
            ListNode dummy(0), *prev = &dummy;
            dummy.next = head;
            int sz = 1;//cur merge size
            int n = 0;//list.size() 
            for(ListNode* p = head; p; ++n, p = p->next); //Get Length
            for(int sz = 1; sz/2 < n; sz += sz) {
                prev = &dummy;
                while(1) {
                    ListNode* l1 = prev->next, *l2, *rest;               
                    for(int steps = 0; steps < sz-1 && l1->next; ++steps, l1 =l1->next);    //ready to set up list 1
                    if(!l1->next) break;   //if we encounter NULL then nothing to merge
                    l2 = l1->next;    // ready to set up list 2
                    for(int steps = 0; steps < sz-1 && l2->next; ++steps, l2 = l2->next);
                    rest = l2->next;   // mark the beginning of the rest of the list
                    l2->next = NULL;   // NULL the end of list 2
                    l2 = l1->next;        // set the head of list 2
                    l1->next = NULL;  //NULL the end of list 1
                    l1 = prev->next;   //set the head of list 1
                    ListNode* newTail;    // one of the output of the merge function, i.e., the tail of the merged list
                    l1 = merge(l1, l2, newTail);   
                    prev->next = l1;
                    newTail->next = rest;
                    prev = newTail;
                    if(!rest) break;
                } 
            }
            return dummy.next;
        }
    
        ListNode* merge(ListNode*l1, ListNode* l2, ListNode* &newTail) { //sz: the size of each sorted list
            ListNode dummy(0);
            newTail = &dummy;
            while(l1 && l2) {
                if(l1->val < l2->val) {
                    newTail->next = l1;
                    l1 = l1->next;
                } else {
                    newTail->next = l2;
                    l2 = l2->next;
                }
                newTail = newTail->next;
            }
            l1 ? newTail->next = l1 : newTail->next = l2;
            for( ; newTail->next; newTail = newTail->next);
            return dummy.next;
        }
    };

Log in to reply
 

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