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

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

/**
 * 
 * @param lists ListNode类一维数组 
 * @return ListNode类
 */

// Recursion
const  mergeTwoLists = (l1, l2) => {
    if (!l1) return l2;
    if (!l2) return l1;
    
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

// Iteration
const  mergeTwoLists = (l1, l2) => {
    if (!l1) return l2;
    if (!l2) return l1;
    
    let dummy = new ListNode(0);
    let p = dummy;
    
    while (l1 && l2) {
        if (l1.val < l2.val) {
            p.next = l1;
            l1 = l1.next;
        } else {
            p.next = l2;
            l2 = l2.next;
        }
        p = p.next;
    } 
    
    if (l1) p.next = l1;
    if (l2) p.next = l2;
    
    return dummy.next;
}

function mergeKLists( lists ) {
    // base cases
    if (lists.length === 0) return null;
    if (lists.length === 1) return lists[0]; 
    if (lists.length === 2) return mergeTwoLists(lists[0], lists[1]);
    
    let mid = Math.floor(lists.length / 2);
    
    let left = mergeKLists(lists.slice(0, mid));
    let right = mergeKLists(lists.slice(mid));
    
    return mergeTwoLists(left, right);
}

module.exports = {
    mergeKLists : mergeKLists
};