题解 | #合并k个已排序的链表#

使用归并思想

static struct ListNode * merge(struct ListNode * h1,struct ListNode * h2){
    struct ListNode * C = NULL;
    if(h1 == NULL || h2 == NULL){
        if(h1 == NULL){
            return h2;
        }else{
            return h1;
        }
    }
    if(h1->val < h2->val){
        C = h1;
        h1 = h1->next;
    }else{
        C  = h2;
        h2 = h2->next;
    }
    struct ListNode * work = C;
    while( h1 != NULL && h2 != NULL){
        if( h1->val < h2->val){
            work->next = h1;
            work = work->next;
            h1 = h1->next;
        }else{
            work->next = h2;
            work = work->next;
            h2 = h2->next;
        }
    }
    if(h1 == NULL){
        work->next = h2;
    }else{
        work->next = h1;
    }
    return C;
}
static struct ListNode * mergeLists(struct ListNode * lists[],int start,int end){
    if(start == end){
        return lists[start];
    }else{
        
        int mid = ( start + end ) / 2;
        struct ListNode * h1 = mergeLists(lists,start,mid);
        struct ListNode * h2 = mergeLists(lists,mid+1,end);
        return merge(h1,h2);
        
    }
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    if(listsLen == 0){
        return NULL;
    }
    return mergeLists(lists,0,listsLen-1);
}