My accepted solution using bottom-up merge sort in C++


  • 1
    D
    class Solution {
    
        public:
        ListNode *sortList(ListNode *head) {
            if(!head || !head -> next) return head;
    
    		ListNode * cur = head;
    		int len = 0;
    		while (cur) len++, cur = cur -> next;
    
    		ListNode * ans = new ListNode(0); 
    		ans -> next = head;
    
    		for (int  width = 1; width < len; width += width){
    
    			ListNode * start1, *end1, *start2, *end2, *last;
    			last = ans;
    
    			while (last -> next) {
    				start1 = last -> next;
    				end1 = move(width, start1);
    				if(end1) start2 = end1; 
    				else 
    					break;
    
    				end2 = move(width, start2);
    				ListNode * next_for_last = end2 ;
    				ListNode * new_last;
    				
    				last -> next = mergeSort(start1, end1, start2, end2, new_last);
    				last = new_last;
    				last -> next = next_for_last;
    			}
    		}
    		return ans -> next;
    	}
        private:
    	ListNode * move (int k, ListNode * cur) {
    		for (int i = 0; i < k && cur; i++) cur = cur -> next;
    		return cur;
    	}
    	ListNode * mergeSort (ListNode * start1, ListNode * end1, ListNode * start2, ListNode * end2, ListNode * &new_last) {
    		if (!start1) return start2;
    		if (!start2) return start1;
    
    		ListNode * merge , *head;
    		if (start1 -> val < start2 -> val) {
    			merge = start1;
    			start1 = start1 -> next;
    		} else {
    			merge = start2;
    			start2 = start2 -> next;
    		}
    		head = merge;
    
    		while (start1 != end1 && start2 != end2) {
    			if (start1->val < start2->val) {
    				merge -> next = start1;
    				start1 = start1 -> next;
    			} else {
    				merge -> next = start2;
    				start2 = start2 -> next;
    			}
    			merge = merge -> next;
    		}
    		while (start1 != end1) {
    			merge -> next = start1;
    			start1 = start1 -> next;
    			merge = merge -> next;
    		}
    		while (start2 != end2) {
    			merge -> next = start2;
    			start2 = start2 -> next;
    			merge = merge -> next;
    		}
    		new_last = merge;
    		return head;
    	}
    
    };

  • 0
    I

    elegant!with O(1) memory complexity


  • 0
    W

    The bottom up idea is good and can be used to achieve O(1) memory.

    But I don't think your code uses O(1) memory.

    To achieve O(1), you have to avoid creating new variables or calling other methods inside the loops.


  • 0
    D

    For example inside this loop variables are created only once, compiler creates them at the begining of this metod
    for (int width = 1; width < len; width += width)


  • 0
    W

    I think you are right. I forgot that the memory is reused so no extra memory is needed.


  • 0
    B
    This post is deleted!

  • 0
    B

    It is not possible to have start1 null while start2 not null right?


  • 0
    D

    It is not possible, because I have this if
    {{{ if(end1) start2 = end1;
    else
    break; }}}


Log in to reply
 

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