Merge k Sorted Lists(Hard)

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
 }

public ListNode mergeKLists(ListNode[] lists) {}

解题思路：基于Heap

Time: log(k) * n.

k is number of list and n is number of total elements.

private Comparator<ListNode> ListNodeComparator = new Comparator<ListNode>() {
    public int compare(ListNode left, ListNode right) {
        if (left == null) {
            return 1;
        } else if (right == null) {
            return -1;
        }
        return left.val - right.val;
    }
};

public ListNode mergeKLists(List<ListNode> lists) {
    if (lists == null || lists.size() == 0) {
        return null;
    }

    Queue<ListNode> heap = new PriorityQueue<ListNode>(lists.size(), ListNodeComparator);
    //从每个sorted linked list取一个元素插入heap
    for (int i = 0; i < lists.size(); i++) {
        if (lists.get(i) != null) {
            heap.add(lists.get(i));
        }
    }

    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    while (!heap.isEmpty()) {
        ListNode head = heap.poll();
        tail.next = head;
        tail = head;
        if (head.next != null) {
            heap.add(head.next);
        }
    }
    return dummy.next;
}