# 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 : \[ ]

{% hint style="info" %}
**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.
  {% endhint %}

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

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

**알고리즘을 Java로 구현**

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