Merge k Sorted Lists

Java

//solution 1: PriorityQueue
class Solution {
		public ListNode mergeKLists(List<ListNode> lists) {
		ListNode dummy = new ListNode(-1);
		ListNode cur = dummy;
		PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> (a.val - b.val));
		for (ListNode head : lists) {
			if (head != null) {
				pq.offer(head);
			}
		}
		while (!pq.isEmpty()) {
			ListNode node = pq.poll();
			cur.next = node;
			if (node.next != null) {
				pq.offer(node.next);
			}
			cur = cur.next;
		}
		return dummy.next;
		}
}
Time Complexity : O(nlogk); //PriorityQueue
Space Complexity : O(n); //a new ListNode