Merge sort - bottom up


  • 0

    From pseudo-code of merge sort Wikipedia page:
    https://en.wikipedia.org/wiki/Merge_sort

    
    class Solution {
    public:
    	ListNode* sortList(ListNode* head) 
    	{
    		if (head == nullptr)
    			return head;
    		vector<ListNode*> vlist(32, nullptr);
    		ListNode *curr = head, **left, *right, *follow;
    		ListNode Anchor(0);
    		while (curr)
    		{
    			follow = curr->next;
    			curr->next = nullptr;
    			Anchor.next = curr;
    			int i;
    			for (i = 0; i < 32 && vlist[i]; ++i)
    			{
    				left = &Anchor.next;
    				right = vlist[i];
    				while (*left && right)
    				{
    					if ((*left)->val < right->val)
    						left = &(*left)->next;
    					else
    					{
    						ListNode *temp = *left;
    						*left = right;
    						right = right->next;
    						(*left)->next = temp;
    					}
    				}
    				if (right)
    					*left = right;
    				vlist[i] = nullptr;
    			}
    			if (i == 32)
    				--i;
    			vlist[i] = Anchor.next;
    			Anchor.next = nullptr;
    			curr = follow;
    		}
    		Anchor.next = nullptr;
    		for (int i = 0; i < 32; ++i)
    		{
    			left = &Anchor.next;
    			right = vlist[i];
    			while (*left && right)
    			{
    				if ((*left)->val < right->val)
    					left = &(*left)->next;
    				else
    				{
    					ListNode *temp = *left;
    					*left = right;
    					right = right->next;
    					(*left)->next = temp;
    				}
    			}
    			if (right)
    				*left = right;
    		}
    		return Anchor.next;
    	}
    };
    

Log in to reply
 

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