题解 | #合并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);

struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here

    if (listsLen == 0) return NULL;
    if (listsLen == 1) return lists[0];

    struct ListNode* mhead = NULL;

    while (listsLen--) {    //从后往前进行
        mhead = merge(mhead, lists[listsLen]);
    }
    return mhead;
}

struct ListNode* merge(struct ListNode* p1, struct ListNode* p2) {
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    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;
    }

    struct ListNode* mergedHead = dummy->next;   
    free(dummy);

    return mergedHead;
}

核心：在之前排序的基础上，这里是从后往前进行遍历。