23 Merge k Sorted Lists

合并k个有序链表

利用分治的思想把合并k个链表分成两个合并k/2个链表的任务，一直划分，直到任务中只剩一个链表或两个链表。递推方程为T(k) = 2T(k/2) + O(nk)，算法复杂度为O(nklogk)

分治法，非递归实现，faster than 73%

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int n = lists.length;
        if(n == 0) return null;
        while(n > 1){
            int  k = (n + 1) / 2;
            for(int i = 0; i < n / 2; i++){
                lists[i] = mergeTwoLists(lists[i], lists[i + k]);
            }
            n = k;
        }
        return lists[0];
    }
    private ListNode mergeTwoLists(ListNode l1, ListNode 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;
        }
    }
}

分治法的递归实现，faster than 80%

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int n = lists.length;
        if(n == 0) return null;
        return recursive(lists, 0, n - 1);
    };
    public ListNode recursive(ListNode[] lists, int l, int r){
        if(l == r) return lists[l];
        int mid = (l + r) / 2;
        ListNode l1 = recursive(lists, l, mid);
        ListNode l2 = recursive(lists, mid + 1, r);
        return mergeTwoLists(l1, l2);
    };
    public ListNode mergeTwoLists(ListNode l1, ListNode 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;
        }
    }
}

普通队列，先进先出，队尾追加元素，队头删除元素。
优先队列，元素被赋予优先级，通常采用堆数据结构实现。
最小优先队列，查找删除操作首先对于优先权较小的元素执行。
最大优先队列，查找删除操作用来对优先权较大的元素执行。

维护一个k个大小的最小堆，初始化堆中元素为每个链表的头节点，每次从堆中选择最小的元素加入到结果链表，再选择该最小元素所在链表的下一个节点加入到堆中。当堆为空时，所有链表的节点都已经加入到结果链表中。元素加入到堆中的复杂度为O(logk)，总共有kn个元素加入堆中，复杂度为nkO(logk)

faster than 46%

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i = 0; i < lists.length; i++){
            while(lists[i] != null){
                queue.offer(lists[i].val);
                lists[i] = lists[i].next;
            }
        }
        return getMin(queue);
    }
    public ListNode getMin(PriorityQueue<Integer> queue){
        if(!queue.isEmpty()){
            ListNode min = new ListNode(queue.poll());
            min.next = getMin(queue);
            return min;
        }
        return null;
    }
}

• Runtime: 340 ms, faster than 32.57%
• Memory Usage: 48.1 MB, less than 6.83%

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    if (lists.length === 0) return null
    let res = lists[0]
    for(let i = 1; i < lists.length; i++) {
        res = mergeTwoLists(res, lists[i])
    }
    return res
};

var mergeTwoLists = function(l1, l2) {
    let dummy = new ListNode(0)
    let res = dummy
    while(l1 && l2) {
        if(l1.val < l2.val) {
            res.next = new ListNode(l1.val)
            l1 = l1.next
        } else {
            res.next = new ListNode(l2.val)
            l2 = l2.next
        }
        res = res.next
    }
    if (l1) {
        res.next = l1
    } else {
        res.next = l2
    }
    return dummy.next
};