/**

  * Definition for singly-linked list.

  * public class ListNode {

  *     int val;

  *     ListNode next;

  *     ListNode(int x) {

  *         val = x;

  *         next = null;

  *     }

  * }

  */

 public class Solution {

     //implements interface listNodeComparator to tell the heap how to compare two elements

     private Comparator<ListNode> listNodeComparator = new Comparator<ListNode>() {

         @Override

         public int compare(ListNode o1, ListNode o2) {

             // TODO Auto-generated method stub

             if(o1 == null)

                 return 1;

             else if(o2 == null)

                 return -1;

             return o1.val-o2.val;

         }

     };

     public ListNode mergeKLists(List<ListNode> lists) {

         if(lists == null || lists.size() == 0)

             return null;

         //Using a priority queue as heap

         Queue<ListNode> heap = new PriorityQueue<ListNode>(lists.size(),listNodeComparator);

         //add all head nodes of k lists into the heap

         for(int i = 0;i < lists.size();i++)

             if(lists.get(i) != null)

                 heap.add(lists.get(i));

         ListNode answer = new ListNode(0);

         ListNode kepler = answer;

         while(!heap.isEmpty()){

             ListNode head = heap.poll();

             kepler.next = head;

             kepler = head;

             //if the list which we just extract elements from still has element,add it into the heap

             if(head.next != null)

                 heap.add(head.next);

         }

         return answer.next;

     }

 }