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

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

struct ListNode* merger(struct ListNode** lists, int listsLen, int left, int right) {
    if(left == right) return lists[left];
    else {
        int mid = left + (right - left) / 2;
        struct ListNode* leftHead = merger(lists, listsLen, left, mid);
        struct ListNode* rightHead = merger(lists, listsLen, mid + 1, right);
        struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* pre = newHead, *p1 = leftHead, *p2 = rightHead;
        while(p1 && p2) {
            if(p1->val < p2->val) {
                pre->next = p1;
                pre = p1;
                p1 = p1->next;
            } else {
                pre->next = p2;
                pre = p2;
                p2 = p2->next;
            }
        }
        if(p1) {
            pre->next = p1;
        } else if(p2) {
            pre->next = p2;
        }
        pre = newHead->next;
        free(newHead);
        return pre;
    }
}


struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    if(listsLen == 0) return NULL;
    return merger(lists, listsLen, 0, listsLen - 1);
}