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

对折合并

struct ListNode* merge(struct ListNode* head1,struct ListNode* head2){
    if(!head1){
        return head2;
    }
    if(!head2){
        return head1;
    }
    struct ListNode* head;
    if(head1->val<=head2->val){
        head=head1;
        head->next=merge(head1->next, head2);
    }
    if(head1->val>head2->val){
        head=head2;
        head->next=merge(head1, head2->next);
    }
    return head;
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    if(listsLen==0){
        return lists[0];
    }
    while(listsLen!=1){
        for(int i=0;i<listsLen/2;i++){
            lists[i]=merge(lists[i],lists[listsLen-i-1]);
        }
        listsLen=(listsLen % 2)?(listsLen / 2 + 1):(listsLen / 2);
    }
    return lists[0];
}