23. 合并K个升序链表——hard-分治 递归

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists

思路：**
与21.合并两个有序链表类似，这次我们需要合并K个升序链表，可以想到我们通过分治来完成：

• 将每两个链表合并，k个升序链表变为k/2个升序链表

重复这个过程，最终只剩下一个一个升序链表。
复杂度分析：（抄自官方题解）

var mergeKLists = function (lists) {
    const merge = (lists, l, r) => {
        if (l === r) return lists[l];
        if (l > r) return null;
        let mid = (l + r) >> 1;
        return mergeList(merge(lists, l, mid), merge(lists, mid + 1, r));
    };
    const mergeList = (a, b) => {
        if ((!a) || (!b)) return a ? a : b;
        let head = new ListNode();
        let cur = head;
        let aPtr = a;
        let bPtr = b;
        while (aPtr && bPtr) {
            if (aPtr.val < bPtr.val) {
                cur.next = aPtr;
                aPtr = aPtr.next;
            } else {
                cur.next = bPtr;
                bPtr = bPtr.next;
            }
            cur = cur.next;
        }
        cur.next = aPtr ? aPtr : bPtr;
        return head.next;
    };
    return merge(lists, 0, lists.length - 1);
};