(Linked List, Hard) Merge k Sorted Lists

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

난이도가 Hard라서 덜덜한데 뭔가 이전 문제랑 아이디어가 비슷할 것 같다.
Dummy 포인터 주고서 배열들 중 가장 낮은 값으로 이어붙이면 되는 것 아닌가?

근데 중요한건 개별 Linked List들이 몇 개가 있을지 모른다는 거다.
순회 로직이 필요하고, 낮은 값 기준으로 그 중 누구를 선택할지 결정해야 한다.

그러면 딱 떠오르는건 우선순위 큐인데..

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;
    }
}

남들 한거 찾아보니 분할정복으로 풀기도 하고,
아니면 리스트 0번 노드를 고정값으로 하고 1번 리스트부터 순회하면서 i번째 노드와 직접비교 (이전 문제와 동일 로직) 하기도 한다.

여러가지 방법이 많은 것 같다.