Merge K Sorted Lists

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

Example :

1 -> 10 -> 20
4 -> 11 -> 13
3 -> 8 -> 9

will result in

1 -> 3 -> 4 -> 8 -> 9 -> 10 -> 11 -> 13 -> 20
Solution:

Time: O(nlogk)
Space: O(k)

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     public int val;
 *     public ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> a) {
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>(){
            @Override
            public int compare(ListNode A, ListNode B) {
                return Integer.compare(A.val, B.val);
            }
        });
        for (ListNode node : a) {
            pq.add(node);
        }
        while (!pq.isEmpty()) {
            ListNode next = pq.poll();
            p.next = next;
            p = p.next;
            if (next.next != null) {
                pq.add(next.next);
            }
        }
        return dummy.next;
    }
}