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

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 * 
 * @param lists ListNode类一维数组 
 * @return ListNode类
 */
function mergeKLists(lists) {
    // write code here
    // 合并当前的两个列表
    function mergeList(list1, list2) {
        // 若其中一个为空，则返回另一个即可
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        // 合并的新列表
        let temp = new ListNode(0);
        let pre = temp;
        while (list1 != null && list2 != null) {
            pre.next = new ListNode(0);
            pre = pre.next;
            if (list1.val < list2.val) {
                pre.val = list1.val;
                list1 = list1.next;
            } else {
                pre.val = list2.val;
                list2 = list2.next;
            }
        }
        while (list1 != null) {
            pre.next = new ListNode(0);
            pre = pre.next;
            pre.val = list1.val;
            list1 = list1.next;
        }
        while (list2 != null) {
            pre.next = new ListNode(0);
            pre = pre.next;
            pre.val = list2.val;
            list2 = list2.next;
        }
        return temp.next;
    }
    // 拆分数组
    function splitList(l, r) {
        if (l > r) {
            return null;
        } else if (l == r) {
            // 当l==r，则代表只有一个列表，此时可以进行返回
            return lists[l];
        }
        // 取中间值进行分治
        let mid = parseInt((l + r) / 2);
        // 开始向下分解列表
        return mergeList(splitList(l, mid), splitList(mid + 1, r));
    }

    let ans = splitList(0, lists.length - 1);
    // console.log("ans:", ans);
    return ans;
}
module.exports = {
    mergeKLists: mergeKLists
};