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

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    struct ListNode* yhead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* cur = yhead;
    while (pHead1 && pHead2) {
        if (pHead1->val <= pHead2->val) {
            cur->next = pHead1;
            pHead1 = pHead1->next;
        } else {
            cur->next = pHead2;
            pHead2 = pHead2->next;
        }
        cur = cur->next;
    }
    cur->next = pHead1 ? pHead1 : pHead2;
    return yhead->next;
}
/**
 *
 * @param lists ListNode类一维数组
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    //只有一个链表或者空链表
    if (listsLen <=1) {
        return *lists;
    }
    while (1) {
        for (int i = 0; i < listsLen / 2; i++) {
            lists[i] = Merge(lists[i], lists[listsLen - i - 1]);
        }
        if (listsLen == 2) {
            break;
        }
        listsLen = listsLen % 2 == 1 ? listsLen / 2 + 1 : listsLen / 2;
    }
    return *lists;
}