# Java solution with explanation using priority queue

• The priority queue is used to solve the problem. As for the priority, it is very important to know how to
set up the comparator.

``````PriorityQueue<Integer> queue = new PriorityQueue<Integer>();

while(!queue.isEmpty()){
System.out.print(queue.poll()+ ",");
}

// The result above is 1,2,3;
``````

The default order is ascending order.

1. As for number the smallest will be at the head;
2. As for string it is sorted alphabetically；
3. Also can be sorted based on the comparator.
In this problem, the object is the node, we have to set up
what to use to compare different nodes. Below shows a brief example to show how to set up a comparator.

As the code shows, we have to set up a comparator;

``````Comparator cmp;
cmp = new Comparator(){
public int compare(ListNode o1, ListNode l2){
@Override
return o1-o2;// the nodes will be in ascending order;
//          return o2-o1 // the nodes will be in descending order;
}
};

``````
``````PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(lists.length, cmp);
// don't worry about the lists.length, you can also set up to 1 if you like,
// as you add more nodes in the queue, the size will be enlarged as well.
``````

The left part will be easy to understand, put all the head of each list into the priority, poll() the smallest and add its next if its next exists.

Correct me if I am wrong. Thx!!!!

``````
/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length ==0) return null;

Comparator<ListNode> cmp = new Comparator<ListNode>(){
@Override
public int compare(ListNode o1, ListNode o2){
return o1.val-o2.val;
}
};
PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(lists.length, cmp);

ListNode dummy = new ListNode(0);

for(ListNode nodes : lists){
if(nodes != null){
}
}
while(!queue.isEmpty()){