A different non-recursive solution using a stack of O(log n) space


  • 0
    Z

    I am not trying to spit the list into two equal halves. I use a stack to store the heads of lists of 2^i sizes. My algorithm works as this:

    1. Loop through all element.
      1. Make it as a length 1 list, named q.
      2. Keep merging q with the top of stack as long as they have the same size.
      3. Push q to stack.
    2. Merge everything left in the stack.

    The algorithm can be proved also runs in O(n log n) time.
    Can you prove it? :))

    class Solution {
    public:
    
    ListNode *sortList(ListNode *head) {
        stack<pair<ListNode *, int> > s;
        ListNode *p=head, *q=0;
        int len=0;
        
        if(head==0) return 0;
        while (p) {
            q=p;
            len=1;
            p=p->next;
            q->next=0;
            
            while( !s.empty() && s.top().second==len ) {
                ListNode * tmp = s.top().first;                
                int tmplen=s.top().second;
                s.pop();
                
                q = mergeList(tmp,q);
                len +=tmplen;
            }
            s.push(make_pair(q,len));
        }
        
        q = s.top().first; 
        len=s.top().second;
        s.pop();       
        
        while(!s.empty()) {
    
            ListNode * tmp = s.top().first;                
            int tmplen=s.top().second;
            s.pop();
            
            q = mergeList(tmp,q);
            len +=tmplen;
        }
        
        return q;        
    }
    
    
    ListNode *mergeList(ListNode *h1, ListNode* h2)
    {
    	ListNode *p1 = h1, *p2 = h2;
    
    	ListNode *h = 0, *t = 0;
    	while (p1 || p2) {
    		if (p1 && p2) {
    			if (p1->val <= p2->val){
    				if (h) t = t->next = p1;
    				else t = h = p1;
    				p1 = p1->next;
    			}
    			else {
    				if (h) t = t->next = p2;
    				else t = h = p2;
    				p2 = p2->next;
    			}
    		}
    		else if (p1) {
    			if (h) t = t->next = p1;
    			else t = h = p1;
    			p1 = p1->next;
    		}
    		else {
    			if (h) t = t->next = p2;
    			else t = h = p2;
    			p2 = p2->next;
    		}
    	}
    	if (t) t->next = 0;
    	return h;
    }
    };

Log in to reply
 

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