【算法解析LeetCode by Javascript】23. 合并K个排序链表

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

var isOver = function (lists) {
    let r = true
    lists.map(val => {
        if (val) {
            r = false
            return r
        }
    })
    
    return r
}

var minNode = function (lists) {
    let val = null
    let j
    for (var i = 0; i < lists.length; i++) {
        if (lists[i]) {
            if (val === null) {
                val = lists[i].val
            }
            // console.log(lists[i].val, val)
            if (lists[i].val <= val) {
                val = lists[i].val
                j = i
            }
        }
    }
    console.log(j)
    let m = new ListNode(lists[j].val)
    lists[j] = lists[j].next
    
    return m
}

var mergeKLists = function(lists) {
    if (lists.length === 0) return ''
    let result = null
    while (!isOver(lists)) {
        if (!result) {
            result = minNode(lists)
        } else {
            let z = result
            while (z.next) {
              z = z.next
            }
            z.next = minNode(lists)
        }
    }
    
    return result
    
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    if(lists.length == 0) return null;
    var k = lists.length;
    while(k > 1){
        for (let i = 0; i < ~~(k / 2); i++) {
            lists[i] = mergeTwoLists(lists[i], lists[i + ~~((k + 1) / 2)]);
        }
        k = ~~((k + 1) / 2);
    }
    return lists[0];
};
var mergeTwoLists = function (l1, l2) {
    if (l1 == null) return l2
    if (l2 == null) return l1
    if (l1.val <= l2.val) {
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    } else {
        l2.next = mergeTwoLists(l1, l2.next)
        return l2
    }
}