23. Merge k Sorted Lists

Problem Statement

Pattern:

---

Merge Solution

250ms O(n^2) and recursion → function calling time O(1) space complexity Merge Sort Solution

ListNode merge(ListNode a, ListNode b) {
	if(a == null) return b;
	if(b == null) return a;
 
	ListNode smaller, larger;
 
	smaller = (a.val <= b.val) ? a : b;
	larger = (b.val >= a.val) ? b : a;
 
	smaller.next = merge(smaller.next, larger);
	return smaller;
}
 
public ListNode mergeKLists(ListNode[] lists) {
	int n = lists.length;
	if(n == 0) return null;
	if(n == 1) return lists[0];
	
	ListNode curr = new ListNode(Integer.MIN_VALUE);
	
	for(ListNode list : lists) 
		curr =  merge(curr, list);
	
	return curr.next;
}

PQ Solution

16 ms, O(n) space

public static ListNode mergeKLists(ListNode[] lists) {
	PriorityQueue<ListNode> pq =
		new PriorityQueue<ListNode>(Comparator.comparingInt((ListNode a) -> a.val));
	
	for(ListNode nodeHead : lists)
		if(nodeHead != null) pq.add(nodeHead); // avoid NPE
	
	ListNode sortedLL = new ListNode(-1), sortedLLHead = sortedLL;
	
	while (!pq.isEmpty()) {
		ListNode minNode = pq.poll();
		sortedLL.next = new ListNode(minNode.val);
		sortedLL = sortedLL.next;
		if(minNode.next != null) pq.add(minNode.next);
	} 
	return sortedLLHead.next;
}
 

Notes

• Add the heads of LLs to a priority queue that can compare the value at the current node
• pop each node off the min heap, and add to sorted linked list
  • add node back to heap if there node.next != null
  • repeat till pq is empty