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

#include <stdio.h>
#include <stdlib.h>

typedef int data_t;
 struct ListNode{
    data_t val;
    struct ListNode *next;
};


struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {

    //防止pHead1或pHead2为空
    if(pHead1->next==NULL)
    {
        return pHead2;
    }
    if(pHead2->next==NULL)
    {
        return pHead1;
    }

    //定义返回链表
    struct ListNode* cur=malloc(sizeof(struct ListNode));
    cur->next = NULL;

    //作为返回链表的头
    struct ListNode* res = cur;

    pHead1 = pHead1->next;
    pHead2 = pHead2->next;

    while(pHead1!=NULL&&pHead2!=NULL)
    {
        if(pHead1->val<=pHead2->val)
        {
            cur->next=pHead1;
            cur=cur->next;
            pHead1=pHead1->next;
        }
        else
        {
            cur->next=pHead2;
            cur=cur->next;
            pHead2=pHead2->next;
        }
    }
    //若是有一边链表未遍历完，可直接指向当前节点，原链表已排好序
    if(pHead1!=NULL)
    {
        cur->next=pHead1;
    }
    if(pHead2!=NULL)
    {
        cur->next=pHead2;
    }
    return res;
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {

    if(listsLen==0)
        return NULL;

    for (int i = 1; i < listsLen; ++i) {
        lists[0] = Merge(lists[0],lists[i]);
    }

    return lists[0];
}
//节点插入
void node_insert(struct ListNode* head, data_t x){

    struct ListNode* node = (struct ListNode*) malloc(sizeof(struct ListNode));
    node->val = x;
    while (head->next != NULL){
        head = head->next;
    }

    node->next = head->next;
    head->next = node;

}
/**
 * 递增链表创建
 * @param start 起始大小
 * @param num 链表长度
 * @return
 */
struct ListNode* list_create(int start, int num){
    struct ListNode* list = (struct ListNode*) malloc(sizeof(struct ListNode));
    list->next = NULL;

    for (int i = 0; i < num; ++i) {
        node_insert(list,i+start);
    }

    return list;
}

int main(){

    struct ListNode* list1 = list_create(1,4);
    struct ListNode* list2 = list_create(2,1);
    struct ListNode* list3 = list_create(1,0);
    struct ListNode* list4 = list_create(5,4);

    struct ListNode *list[4] = {list1,list2,list3,list4};

    struct ListNode* res = mergeKLists(list,4);

    while (res->next != NULL){
        printf("%d ",res->next->val);
        res = res->next;
    }
    printf("\n");


    return 0;
}