Share my 11 ms C solution-using recursive and binary mind


  • 3

    more solutions see: https://github.com/lightmen/leetcode.git

    struct ListNode *mergeTwoLists(struct ListNode *list1, struct ListNode *list2)
    {

    struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *cur = head;
    while(list1 && list2){
        if(list1->val > list2->val){
            cur->next = list2;
            list2 = list2->next;
        }else{
            cur->next = list1;
            list1 = list1->next;
        }
        cur = cur->next;
    }
    
    if(list1){
        cur->next = list1;
    }else{
        cur->next = list2;
    }
    
    cur = head->next;
    free(head);
    return cur;
    

    }

    struct ListNode *merge(struct ListNode *lists[],int beg,int end){

    if(beg > end)
        return NULL;
    if(beg == end)
        return lists[beg];
        
    int mid = (beg + end) / 2;
    struct ListNode *left = merge(lists,beg,mid);
    struct ListNode *right = merge(lists,mid+1,end);
    
    return mergeTwoLists(left,right);
    

    }

    struct ListNode *mergeKLists(struct ListNode *lists[], int k)
    {

    return merge(lists,0,k-1);
    

    }


  • 0
    D

    I have the same idea, but it seems hard to be within 100ms


  • 0

    yeah, I had test it again using the same code, it's 456 ms now. Maybe the OJ system had changed.


  • 0
    Y

    I also have the same idea. It costs 399 ms. In addition, last day I put it on OJ but it returned 'time exceeded'. But today, I change nothing and It pass all the tests.


Log in to reply
 

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