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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param lists ListNode类一维数组 
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
 struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    if (l1 == NULL) {
        return l2;
    } else if (l2 == NULL) {
        return l1;
    } else if (l1->val < l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}
struct ListNode* mergeKLists(struct ListNode** lists, int k) {
    if (k == 0) {
        return NULL;
    } else if (k == 1) {
        return lists[0];
    } else if (k == 2) {
        return mergeTwoLists(lists[0], lists[1]);
    } else {
        int mid = k / 2;
        struct ListNode* left = mergeKLists(lists, mid);
        struct ListNode* right = mergeKLists(lists + mid, k - mid);
        return mergeTwoLists(left, right);
    }
}