Merge k Sorted Lists

★★☆☆☆

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

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 a,ListNode b){
            return a.val - b.val;
        }
    });
    ListNode dummy = new ListNode(0);
    ListNode ptr = dummy;

    for (ListNode node: lists) {
        if (node != null) queue.offer(node);
    }

    while (!queue.isEmpty()) {
        ptr.next = queue.poll();
        ptr = ptr.next;
        if (ptr.next != null) queue.offer(ptr.next);
    }

    return dummy.next;
}