23. Merge k Sorted Lists

# Hard

用堆来实现弹出，一共只有k个元素，堆每次弹出最小的数的操作是 $O(1)$ ，堆每次删除和修改的操作需要 $O(lgk)$ ，这道题的时间复杂度是 $O(nlgk)$

Java(O(KN)

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int min_index = 0;
        ListNode dump = new ListNode();
        ListNode h = dump;
        while(true) {
            boolean isBreak = true;
            int min = Integer.MAX_VALUE;
            for(int i = 0; i < lists.length; i ++) {
                if(lists[i] != null) {
                    if(lists[i].val < min) {
                        min_index = i;
                        min = lists[i].val;
                    }
                    isBreak = false;
                } 
            }
            if(isBreak)
                break;
            ListNode temp = new ListNode(lists[min_index].val);
            h.next = temp;
            h = h.next;
            lists[min_index] = lists[min_index].next;
        }
        h.next = null;
        return dump.next;
    }
}

Java(O(NlgK), priorityQueue)

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        Comparator<ListNode> cmp = new Comparator<ListNode>() {
            @Override
            public int compare(ListNode n1, ListNode n2) {
                return n1.val - n2.val;
            }
        };
        
        Queue<ListNode> q = new PriorityQueue<ListNode>(cmp);
        for(ListNode l : lists) {
            if(l != null) {
                q.add(l);
            }
        }
        ListNode dump = new ListNode();
        ListNode p = dump;
        while(!q.isEmpty()) {
            p.next = q.poll();
            p = p.next;
            ListNode next = p.next;
            if(next != null)
                q.add(next);
        }
        return dump.next;
    }
}java