# 23 Merge k Sorted Linked List

input是一個ListNode[]，每個element是一個linked list的頭， 要把所有linked list組合成一個，並sorted。

Concept: 把所有ListNode排序，可以用PriorityQueue，寫Comparator使數字小得排在上面。 先依序讀取所以lists中的所有ListNode，丟進PriorityQueue就會自動排序， Create ListNode head 當新的頭，ListNode ptr來依序前進， 從queue中依序poll()，排進head。

Implementation: 要注意的地方

1. PriorityQueue Comparator: int compare(ListNode p, ListNode q) p.val < q.val，p要排在前面，要回傳-1，反之回傳1。
2. 從queue中poll出來並串起來的時候: 每poll出一個ListNode，若該ListNode的next還有東西，要加入queue。

Code:

/**
 * Definition for singly-linked list.
 * 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;
        PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(lists.length,new Comparator<ListNode>(){
            @Override
            public int compare(ListNode p, ListNode q){
                return p.val < q.val ? -1 : 1;
            }
        });
        for(ListNode node: lists){
            if(node!=null)
                queue.add(node);
        }
        ListNode head = new ListNode(0);
        ListNode ptr = head;
        while(!queue.isEmpty()){
            ptr.next = queue.poll();
            ptr = ptr.next;
            if(ptr.next!=null)
                queue.add(ptr.next);
        }
        return head.next;
    }
}