Merge K Sorted Lists

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1: Input : lists = [[1,4,5],[1,3,4],[2,6]] Output : [1,1,2,3,4,4,5,6]

Example 2 : Input : lists = [ ] Output : [ ]

Example 3 : Input : lists = [[ ]] Output : [ ]

Constraints :

• k == lists.length

• 0 <= k <= 10^4

• 0 <= lists[i].length <= 500

• -10^4 <= lists[i][j] <= 10^4

• lists[i] is sorted in ascending order.

• The sum of lists[i].length won't exceed 10^4.

자료구조 : 우선순위 큐(=정렬), 링크드리스트 이용

알고리즘 1. 자료구조 생성 2. 우선순위 큐(오름차순 정렬)에 데이터 넣는다. 3. 큐에서 데이터 빼면서 정답리스트에 넣는다.//+큐에서 빼려는 데이터의 다음 노드가 Null이 아니면 node.next를 큐에 넣는다.

알고리즘을 Java로 구현

/**
 * 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) {
        //1.자료구조 생성
        ListNode dummyHead = new ListNode(0);
        ListNode p = dummyHead;
        PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(Comp);
        
        //2.큐에 데이터 담기
        for(ListNode node : lists) {
            if(node != null) {
                queue.offer(node);
            }
        }
        //3.큐에서 데이터 빼면서 정답 리스트에 담기
        while(!queue.isEmpty()) {//비지 않는 동안만(데이터가 있을 때만).
            ListNode node = queue.poll();
            p.next = node;
            p = p.next;
            if(node.next != null) {
                queue.offer(node);
            }
        }
        return dummyHead.next;
    }
    Comparator<ListNode> Comp = new Comparator<ListNode>(){
        public int compare(ListNode l1, ListNode l2) {
            return l1.val - l2.val;//ascending order
        }
    };
}