【アルゴリズム解析LeetCode by Javascript】23.Kの並べ替えチェーンを統合する

Kの並べ替えリストを結合
k個の並べ替えチェーンを結合して、結合後の並べ替えチェーンを返します.アルゴリズムの複雑さを解析して説明してください.
例:

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

1.暴力解読法
この解法は暴力的すぎるので、慎重に使ってください.
原理はすべてのノードを分解して並べ替えて、また新しいものから一つのリストに結合して、道理は分かりやすいです.
時間複雑度はO(nlogn)です.
2.列挙法
この解法の主な考え方はすべてのリストのヘッダ値を巡回して、最小の一つを現在の結果キューに押し込むことです.
具体的な解法は

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
    
};

極限の場合は要素を得るたびに、k個のチェーンを遍歴する必要があります.複雑さはO(kn)で、k値の複雑さは高いです.方法よりも速くないです.
3.分割法
私達は隣のリストを統合するだけで、このようにすれば、私達はlogN回の操作だけでリストを整理して整理リストにすることができます.
再帰的深さは全部でlogkであり、各層の再帰的な動作回数は全部n回であり、nは全ての要素の個数である.全体の複雑さは
O(nlogk)

/**
 * 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
    }
}

送信