문제

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

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>((o1, o2) -> {
            if (o1.val == o2.val){
                return 0;
            } else if(o1.val > o2.val){
                return 1;
            } else {
                return -1;
            }
        });

        for(ListNode node: lists){
            if (node != null) pq.add(node);
        }

        ListNode root = new ListNode(0);
        ListNode tail = root;

        while (!pq.isEmpty()){
            tail.next = pq.poll();
            tail = tail.next;

            if (tail.next != null){
                pq.add(tail.next);
            }
        }
        return root.next;
    }

}

처음에는 주어진 노드들을 모두 Priority Queue에 넣어두고 하나씩 뽑아서 연결할 생각을 하였다.

하지만, 주어진 리스트들이 정렬되어 있는 상태였기 때문에 해당 리스트들의 가장 앞의 원소들만 두고 생각을 해도 충분하였다.

1. 각 리스트의 가장 작은 원소들 PQ에 넣기.
2. PQ에서 가장 우선순위 높은 것(.poll()) 뽑아서 연결하기.
3. 2번에서 뽑은 노드의 다음 원소 존재할 경우 PQ에 넣기
4. 1 ~ 3 반복

위 과정을 반복하면서 하나의 정렬된 리스트를 만들 수 있다.