合并k个已排序的链表

// 既然是lists是数组，那就循环遍历，每次找到链表头值最小的那个索引，在进行拼接
function mergeKLists( lists ) {
    let res = new ListNode(0)
    let curr = res
    while(true){
        let idx = -1
        for(index in lists){
            if(lists[index] == null) continue
            else if(idx == -1) idx = index
            else if(lists[index].val < lists[idx].val){
                idx = index
            }
        }
        if(idx == -1) break
        curr = curr.next = lists[idx]
        lists[idx] = lists[idx].next
    }
    return res.next
}

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

/**
 * 
 * @param lists ListNode类一维数组 
 * @return ListNode类
 */
function merge( lists, left, right) {
    if (left >= right)
        return lists[left]
    let mid = ~~((left + right) / 2);
    let l = merge( lists, left, mid);//返回左区间指针
    let r = merge( lists, mid + 1, right);//返回右区间指针
    let head = new ListNode(-1);
    let temp = head;
    while (l != null && r != null) {

        if (l.val <= r.val) {
            temp.next = l
            temp = l;
            l = l.next;
        } else {
            temp.next = r
            temp = r;
            r = r.next;
        }
    }
    if (l != null) {
        temp.next = l
    }
    if (r != null) {
        temp.next = r
    }
    return head.next;
}

function mergeKLists(lists) {
   return merge(lists, 0, lists.length - 1);
}
module.exports = {
    mergeKLists : mergeKLists
};

主要有两个比较好的方法，一个是堆，一个是分治。

js写这个题。如果使用堆(优先队列)的话，难点是需要自己实现堆的数据结构。c或java好像都有内置已经写好的优先队列数据解构。

js利用数组实现堆需要注意的是：

1. push添加元素的时候，向数组尾部添加元素，如果向其他位置添加元素的话(比如数组开头)，会整个打乱堆，需要重新初始化堆。如果向尾部添加元素，只需要重新初始化树的一半就行。
2. 如果要删除开头元素。将开头元素后尾部元素交换后在删除尾部元素。因为直接删除打乱了整个堆的解构，需要重新初始化，而删除尾部元素不会打乱堆，可以只初始化一边。

function mergeKLists( lists ) {
    if (lists.length <= 1) return lists[0] || null;
    let heap = new minHeap(), head = {next: null}, p = head;
    for (let i=0; i<lists.length; ++i) {
        if (lists[i]) {
            heap.push(lists[i]);
        }
    }
    while(heap.heap.length) {
        p.next = heap.pop();
        p = p.next;
        if (p.next) {
             heap.push(p.next);
        }
    }
    return head.next;
}
class minHeap {
    constructor() {
        this.heap = [];
    }
    push(node) {
        this.heap.push(node);
        let i = this.heap.length-1, dad = Math.floor((i-1)/2);
        while(dad >= 0) {
            this.minHeap(dad, i);
            dad = Math.floor((dad-1)/2);
        }
    }
    pop() {
        const i=0, j=this.heap.length-1;
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]
        const res = this.heap.splice(j, 1);
        this.minHeap(0, j-1);
        return res[0];
    }
    minHeap(l, r) {
        let dad = l, son = dad*2+1;
        if (son > r) return;
        if (son + 1 <= r && this.heap[son+1].val < this.heap[son].val) {
            ++son;
        }
        if (this.heap[son].val < this.heap[dad].val) {
            [this.heap[dad], this.heap[son]] = [this.heap[son], this.heap[dad]]
            this.minHeap(son, r);
        }
    }
}

分治法：

function mergeKLists( lists ) {
    if (lists.length <= 1) return lists[0] || null;
    return merge(lists, 0, lists.length-1);
}
function merge(lists, l, r) {
    if (l > r) return null;
    if (l === r) return lists[l];
    const mid = Math.floor((l+r)/2);
    return mergeTwoList(merge(lists, l, mid), merge(lists, mid+1, r));
}
function mergeTwoList (list1, list2) {
    if (!list1 || !list2) return list1 || list2;
    let p1 = list1, p2 = list2, head = {next: null}, p = head;
    while(p1 && p2) {
        if (p1.val > p2.val) {
            p.next = p2;
            p2 = p2.next;
        } else {
            p.next = p1;
            p1 = p1.next;
        }
        p = p.next;
    }
    p.next = p1 || p2;
    return head.next;
}