20 ms C merge sort solution


  • 0
    C
    struct ListNode* mergeSortList(struct ListNode* node, int numNodes) 
    {
        struct ListNode* left = NULL;
        struct ListNode* right = NULL;
        struct ListNode *leftSt = NULL, *leftStCur = NULL;
        int leftNodesNum = 0, leftNodesNumTmp = 0;
        struct ListNode* rightSt = NULL;
        int rightNodesNum = 0;
        int i = 0;
        struct ListNode* ret = NULL;
        struct ListNode* cur = NULL;
        
        // base cases
        if (numNodes == 0)
        {
            return NULL;
        }
        else if (numNodes == 1)
        {
            return node;
        }
        
        // divide
    	leftSt = node;
    	leftNodesNum = numNodes/2;
    
    	rightSt = node;
    	for (i=0; i< leftNodesNum; i++)
    	{
    		rightSt = rightSt->next;
    	}
    	rightNodesNum = numNodes-leftNodesNum;
    
    	// make left list tail with NULL ptr
    	leftStCur = leftSt;
    	leftNodesNumTmp = leftNodesNum;
    	while (--leftNodesNumTmp)
    	{
    		leftStCur = leftStCur->next;
    	}
    	leftStCur->next = NULL;
    
    	left = mergeSortList(leftSt, leftNodesNum);
    	right = mergeSortList(rightSt, rightNodesNum);
        
        // merge
        while (leftNodesNum && rightNodesNum)
        {
            if (left->val < right->val)
            {
                if (cur == NULL)
                {
                    ret = left;
                    cur = left;
                }
                else
                {
                    cur->next = left;
                    cur = cur->next;
                }
                
                leftNodesNum--;
    			left = left->next;
            }
            else
            {
                if (cur == NULL)
                {
                    ret = right;
                    cur = right;
                }
                else
                {
                    cur->next = right;
                    cur = cur->next;
                }
                
                rightNodesNum--;
    			right = right->next;
            }
        }
        
        while (leftNodesNum)
        {
            if (cur == NULL)
            {
                ret = left;
                cur = left;
            }
            else
            {
                cur->next = left;
                cur = cur->next;
            }
                
            leftNodesNum--;
    		left = left->next;
        }
        
        while (rightNodesNum)
        {
            if (cur == NULL)
            {
                ret = right;
                cur = right;
            }
            else
            {
                cur->next = right;
                cur = cur->next;
            }
                
            rightNodesNum--;
    		right = right->next;
        }
    
        return ret;
    } 
     
    struct ListNode* sortList(struct ListNode* head) 
    {
        struct ListNode* nd = head;
        int numNodes = 0;
        
        while (nd)
        {
            numNodes++;
            nd = nd->next;
        }
        
        return mergeSortList(head, numNodes);
    }

Log in to reply
 

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