My C 8ms O(nklogk) solution with Divide and Conquer


  • 0
    T
        struct ListNode* mergeTwo(struct ListNode* l1, struct ListNode* l2);
    
        struct ListNode* mergeKhelper(struct ListNode** lists, int start, int end);
    
        struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
            if(!listsSize)
                return *lists;
            return mergeKhelper(lists,0,listsSize-1);
        }
    
    
    struct ListNode* mergeKhelper(struct ListNode** lists, int start, int end){
             int mid=(start+end)/2;
            if(start==mid)
                return mergeTwo(*(lists+mid),*(lists+end));
           
            return mergeTwo(mergeKhelper(lists,start,mid),mergeKhelper(lists,mid+1,end));
        }
    
        struct ListNode* mergeTwo(struct ListNode* l1, struct ListNode* l2){
            if(l1==l2)
                return l1;
            struct ListNode dummy={0,NULL};
            struct ListNode* temp=&dummy;
            
            while(l1&&l2){
                if(l1->val<=l2->val){
                    temp->next=l1;
                    temp=temp->next;
                    l1=l1->next;
                }
                else{
                    temp->next=l2;
                    temp=temp->next;
                    l2=l2->next;
                }
            }
            
            temp->next=(l1)?l1:l2;
            return dummy.next;
        }

Log in to reply
 

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