Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list.

Analyze and describe its complexity.

Have you met this question in a real interview? 

Yes

Example

Given lists:

[
  2->4->null,
  null,
  -1->null
],

return -1->2->4->null.

/**

 * Definition for ListNode.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int val) {

 *         this.val = val;

 *         this.next = null;

 *     }

 * }

 */ 

 import java.util.PriorityQueue;

public class Solution {

    /**

     * @param lists: a list of ListNode

     * @return: The head of one sorted list.

     */

    public ListNode mergeKLists(List<ListNode> lists) {  

        // write your code here

        if(lists == null || lists.isEmpty()) return null;

        PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(lists.size(), new Comparator<ListNode>(){

            public int compare(ListNode a, ListNode b){

                return a.val - b.val;

            }

        });

        

        for(ListNode node : lists){

            if(node != null){

                pq.add(node);

            }

        }

        ListNode dummy = new ListNode(0);

        ListNode runner = dummy;

        while(!pq.isEmpty()){

            ListNode temp = pq.poll();

            runner.next = temp;

            runner = runner.next;

            if(temp.next != null){

                pq.add(temp.next);

            } 

        }

        return dummy.next;

    }

}