22ms solution in C using Merge Sort


  • 0
    C
    struct ListNode* my_sortList(struct ListNode* head, int list_len) {
        struct ListNode * step;
        int len = list_len;
    
        if(len == -1)
        {
    	    for(step = head, len = 0; step != NULL; step = step->next)
    	    {
    		    ++len;
    	    }
        }
    
        if(len == 0) 
        {
    	    return NULL;
        }
        else if(len == 1) 
        {
    	    return head;
        }
        else if(len == 2)
        {
            if(head->val > head->next->val)
            {
                int temp = head->val;
                head->val = head->next->val;
                head->next->val = temp;
            }
            return head;
        }
        else
        {
            struct ListNode * mid;
            int i;
        
            for(i = 0, mid = head; i < len / 2 - 1; ++i)
            {
                mid = mid->next;
            }
        
            struct ListNode * aa = head;
            struct ListNode * bb = mid->next;
            mid->next = NULL;
        
            struct ListNode * a = my_sortList(aa, len / 2);
            struct ListNode * b = my_sortList(bb, (len & 1) == 0 ? len / 2 : len / 2 + 1);
        
            struct ListNode no_name;
            struct ListNode * r = &no_name;
            r->next = NULL;
        
            while(a != NULL && b != NULL)
            {
                if(a->val < b->val)
                {
                    struct ListNode * save = a;
                    a = a->next;
                    save->next = NULL;
                    r->next = save;
                    r = r->next;
                }
                else
                {
                    struct ListNode * save = b;
                    b = b->next;
                    save->next = NULL;
                    r->next = save;
                    r = r->next;
                }
            }
            if(a == NULL && b != NULL)
            {
                r->next = b;
            }
            else if(a != NULL && b == NULL)
            {
                r->next = a;
            }
        
            return no_name.next;
        }
    }
    
    struct ListNode* sortList(struct ListNode* head) {
        return my_sortList(head, -1);
    }

Log in to reply
 

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