(Heap, Hard) Merge k Sorted Lists

https://leetcode.com/problems/merge-k-sorted-lists/description/

이전에 풀었던 문제 같은데, 간단하게 다시 정리할 수 있다.

각 lists 요소는 ListNode 형태로, 이미 오름차순 정렬된 리스트다.
그러므로 PriorityQueue(우선순위는 node.val 기준)를 사용해서 첫 노드들을 모두 담아준 뒤에, 이후에 큐를 순회하면서 바꿔줄 수 있다.

껍데기용 head를 만들고, 큐에서 뽑은 것들을 순서대로 이어 붙인뒤
마지막에 head.next를 리턴해주면 된다.

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        
        PriorityQueue<ListNode> que = new PriorityQueue<>((n1, n2) -> Integer.compare(n1.val, n2.val));

        ListNode head = new ListNode();
        ListNode current = head;

        for (ListNode node : lists) {
            if (node != null) {
                que.offer(node);
            }
        }

        while (!que.isEmpty()) {
            current.next = que.poll();
            current = current.next;

            if (current.next != null) {
                que.offer(current.next);
            }
        }
        
        return head.next;
    }
}