23.合并K个升序链表[困难]🍉

题目信息

问题解答

暴力解法

记录一个简单的暴力解法，以备不时之需。
https://leetcode-cn.com/submissions/detail/117000815/

const mergeKLists = function(lists) {
    return lists
        // 将所有节点放到一个数组中
        .reduce((acc, list) => {
            while(list !== null) {
                acc.push(list)
                list = list.next     
            }
            return acc
        }, [])
        // 数组排序(从小到大)
        .sort((a, b) => a.val - b.val)
        // 重组链表
        .reduceRight((acc, cur) => {
            cur.next = acc
            return cur
        }, null) 
};

分治策略

分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。 这种算法设计策略叫做分治法。
**
在本题实际运用时，则是将链表两两合并、减少比较的次数。

https://leetcode-cn.com/submissions/detail/117032072/(不知道为啥内存消耗得更大了…)
思路就是先实现一个方法合并两个链表，再递归两两合并。

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
    if(lists.length === 0) {
        return null
    }

    if(lists.length === 1) {
        return lists[0]
    }

    if(lists.length === 2) { 
        return mergeTwoList(lists[0], lists[1])
    }

    const mid = Math.round(lists.length / 2)

    const l1 = []
    for(let i = 0; i < mid; i++) {
        l1[i] = lists[i]
    }

    const l2 = []
    for(let i = mid, j = 0; i < lists.length; i++, j++) {
        l2[j] = lists[i]
    }

    return mergeTwoList(mergeKLists(l1), mergeKLists(l2))
}

function mergeTwoList(l1: ListNode | null, l2: ListNode | null) {
    const dummyHead: any = {}
    //可理解为指针
    let cur = dummyHead

    // 排序两链表
    while(l1 !== null && l2!== null) {
        if(l1.val < l2.val) {
            cur.next = l1
            cur = cur.next
            l1 = l1.next
        } else {
            cur.next = l2
            cur = cur.next
            l2 = l2.next
        }
    }


    if(l1 === null) {
        cur.next = l2
    }

    if(l2 === null) {
        cur.next = l1
    }

    return dummyHead.next
}