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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param lists ListNode类一维数组 
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
#include <stdlib.h>
//时间复杂度  O(nlogn) 
//空间复杂度  O(n)
struct ListNode* SortTwolists(struct ListNode** lists,int l,int r);
struct ListNode* mergeTwolists(struct ListNode* head1,struct ListNode* head2);
void free_list(struct ListNode* head);
struct ListNode* copy_list(struct ListNode* head);
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    if(lists==NULL || listsLen==0){
        return NULL;
    }
    if(lists!=NULL && listsLen==1){
        return lists[0];
    }
    return SortTwolists(lists,0,listsLen-1);
}
struct ListNode* SortTwolists(struct ListNode** lists,int l,int r){
    if(l==r){
        return copy_list(lists[l]);
    }
    if(r==l+1 ){
        return mergeTwolists(lists[l],lists[r]);
    }
    int mid=(l+r)>>1;
    struct ListNode* left=SortTwolists(lists,l,mid);
    struct ListNode* right=SortTwolists(lists,mid+1,r);
    struct ListNode* ret;
    //注意下面,要左右两个部分都非空,才free,否则不free(或者复制(没必要))
    if(left && right){
        ret=mergeTwolists(left,right);
        free_list(left),free_list(right);
    }else{
        ret=left==NULL?right:left;
    }
    return ret;
}
struct ListNode* mergeTwolists(struct ListNode* head1,struct ListNode* head2){
    //一定要先判断head1,head2两个都非空
    if(head1==NULL && head2==NULL){
        return NULL;
    }
    struct ListNode* head,*end,*next;
    head=end=(struct ListNode*)malloc(sizeof(struct ListNode));
    while(head1 && head2){
        //进来head1,head2均不为空
        int val=head1->val>head2->val?head2->val:head1->val;
        end->val=val;
        next=(struct ListNode*)malloc(sizeof(struct ListNode));
        //保持遍历
        end->next=next;
        end=end->next;
        head1->val>head2->val?(head2=head2->next):(head1=head1->next);
    }
    //下面两个while循环只进一个
    while(head1){
        end->val=head1->val;
        if(head1->next){
            next=(struct ListNode*)malloc(sizeof(struct ListNode));
        }else{
            next=NULL;
        }
        head1=head1->next;
        end->next=next;
        end=end->next;
    }
    while(head2){
        end->val=head2->val;
        if(head2->next){
            next=(struct ListNode*)malloc(sizeof(struct ListNode));
        }else{
            next=NULL;
        }
        head2=head2->next;
        end->next=next;
        end=end->next;
    }
    return head;
}
void free_list(struct ListNode* head){
    struct ListNode* next;
    while(head){
        next=head->next;
        free(head);
        head=next;
    }
}
struct ListNode* copy_list(struct ListNode* head){
    //注意是空则直接返回
    if(head==NULL){
         return NULL;
    }
    struct ListNode* ret,*end,*next;
    ret=end=(struct ListNode*)malloc(sizeof(struct ListNode));
    while(head){
        end->val=head->val;
        if(head->next){
            next=(struct ListNode*)malloc(sizeof(struct ListNode));
        }else{
            next=NULL;
        }
        head=head->next;
        end->next=next;
        end=end->next;
    }
    return ret;
}