23. Merge k Sorted Lists

Link

Solution

透過priotiyQuue把 每組最前面的node全部放到queue中，確保queue只有k個元素

然後把最小的poll出來，並從該組中再取一個放回queque中，直到所有元素都處理過

T: O(nlogk) , k是list的長度，表示幾組，n是所有元素的個數

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        
        PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>((a,b) -> Integer.compare(a.val, b.val));
        for(ListNode list : lists){
            if(list != null){
                queue.add(list);
            }
        }
        ListNode dummy = new ListNode(0);
        ListNode node = dummy;
        while(!queue.isEmpty()){
            node.next = queue.poll();
            node = node.next;
            if(node.next != null){
                queue.add(node.next);
            }
        }
        return dummy.next;
    }
}