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

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param lists ListNode类一维数组
 * @param listsLen int lists数组长度
 * @return ListNode类
 */

struct ListNode* merge(struct ListNode* p1, struct ListNode* p2) {
    // write code here
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->val = 0;
    dummy->next = NULL;
    struct ListNode* cur = dummy;

    while(p1 && p2){
        if(p1->val <= p2->val){
            cur->next = p1;
            p1 = p1->next;
        }else{
            cur->next = p2;
            p2 = p2->next;
        }
        cur=cur->next;
    }

    // 解决最后剩下的值，防止丢失
    if(p1){
        cur->next = p1;
    }
    if(p2){
        cur->next = p2;
    }

    return dummy->next;
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    struct ListNode* dummy=NULL;
    while(listsLen--){
        dummy = merge(dummy, lists[listsLen]);
    }
    return dummy;
}