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

struct ListNode* merge(struct ListNode* head1, struct ListNode* head2) {
    struct ListNode *p = head1;
    struct ListNode *q = head2;
    if(p == NULL){
        return q;
    }else if(q == NULL){
        return p;
    }else if(p->val < q->val){
        p->next = merge(p->next, q);
        return p;
    }else{
        q->next = merge(p, q->next);
        return q;
    }
}
struct ListNode* toSortList(struct ListNode* head, struct ListNode* tail) {
    if (head == NULL) {
        return head;
    }
    if (head->next == tail) {
        head->next = NULL;
        return head;
    }
    struct ListNode *slow = head, *fast = head;
    while (fast != tail) {
        slow = slow->next;
        fast = fast->next;
        if (fast != tail) {
            fast = fast->next;
        }
    }
    struct ListNode* mid = slow;
    return merge(toSortList(head, mid), toSortList(mid, tail));
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    if(listsLen == 0) return NULL;
    struct ListNode *dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->val = 0;//初始化
    struct ListNode *pr = dummy;
    for(int i = 0; i < listsLen; i++){
        pr->next = lists[i];
        while(pr->next !=  NULL){
            pr = pr->next;  
        }
    }
    //排序
    return toSortList(dummy->next, NULL);
}