NC51 合并k个已排序的链表

NC51 合并k个已排序的链表

NC51 合并k个已排序的链表

解法一:使用辅助数组

遍历每个链表，将节点的val值push进数组arr中

对arr排序

将排序后的数组转换成链表

返回头结点head

时间复杂度：遍历所有节点O(n)，排序O(nlogn)

空间复杂度：使用和节点数量相等长度的数组，O(n)

function mergeKLists( lists ) {
    let arr = []
    for(let i = 0 ; i < lists.length ; i++){
        let p = lists[i]
        while( p != null){
            arr.push(p.val)
            p = p.next
        }
    }
    arr.sort( (a , b) => a-b )
    function ListNode(x){
        this.val = x;
        this.next = null;
    }
    let head = null
    let rear = null
    for(let j = 0 ; j < arr.length ; j ++){
        let node = new ListNode(arr[j])
        if(head == null){
            head = node
            rear = node
        }else{
            rear.next = node
            rear = node
        }
    }
    return head
}
module.exports = {
    mergeKLists : mergeKLists
};

看了题解之后学习了下面的优先队列的方法，别人题解三个点看着简单，自己实 *** bug重重，下面给出最后自己的思路和js代码

解法二：

使用优先队列来储存链表，按照链表头结点的值从小到大储存，最小的在顶部

由于lists的是无序的，所有还需要排序，这里使用的是sort方法有可能有的为空链表，所有在排序之前还需要将空链表删去，这里使用的是splice方法

1.将队列头链表font取出，将该链表头结点插入目标链表head后，删去该链表头结点、

2.再将该链表放回队列，如果为null则不放回

插入链表使用二分查找第一个大于等于链表头结点val的位置然后插入，当lists为空和font头结点大于lists最后一个链表的头结点时特判一下，可以直接push进lists，其他情况就使用二分查找

重复上面两大步，直到队列为空

时间复杂度：对于每个节点插入代价为logk，k为链表数量，每个节点都需要插入和删除，所有总的时间复杂度为nlogk,n为节点数量

空间复杂度：On

function mergeKLists( lists ) {
    for(let i = 0 ; i < lists.length ; i++){
        if( !lists[i] ){
            lists.splice(i , 1)
            i --
        }
    }
    
    lists.sort((a, b) => (a.val - b.val))
    let head = null
    let rear = null
    while( lists.length != 0){
        let font = lists.shift()
        let node = font
        font = font.next
        console.log( 'node:',node.val)
        if(head == null){
            head = node
            rear = node
        }else{
            rear.next = node
            rear = node
        }
        if(font != null){
            if(lists.length == 0){
                lists.push(font)
            }else if(font.val > lists[lists.length - 1].val){
                lists.push(font)
            }else{
                let index = 0
                let left = 0
                let right = lists.length - 1
                while(left <= right){
                    let mid = Math.floor( (left + right) /2)
                    if(lists[mid].val < font.val){
                        left = mid + 1
                    }else{
                        right = mid - 1
                    }
                }
                index = left
                console.log('index:' ,index)
                lists.splice(index , 0 , font)
            }
            
        }
    }
    return head
}
module.exports = {
    mergeKLists : mergeKLists
};