Problem

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Examples

Example 1:

1
2
3

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

will result in

1

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

Solution

This problem is marked hard, depending on how we solve this problem. This is

Method 1 - Using Min Heap

We should add heads of all k sorted lists. At every instant, you need the minimum of the head of all the k linked list. Once you know the minimum, you can push the node to your answer list, and move over to the next node in that linked list.

The simplest solution is using PriorityQueue as min heap. The elements of the priority queue are ordered according to their natural ordering, or by a comparator provided at the construction time (in this case).

Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public ListNode mergeKLists(ListNode[] lists) {
	if (lists == null || lists.length == 0)
		return null;

	PriorityQueue<ListNode> minHeap = new PriorityQueue<ListNode> (new Comparator<ListNode> () {
		public int compare(ListNode l1, ListNode l2) {
			return l1.val - l2.val;
		}
	});

	for (ListNode list: lists) {
		if (list != null) {
			minHeap.offer(list);
		}
	}

	ListNode head = new ListNode(0); 
	ListNode curr = head;
	while (!queue.isEmpty()) {
		ListNode n = queue.poll();
		curr.next = n;
		curr = curr.next;

		if (n.next != null) {
			minHeap.offer(n.next);
		}
	}

	return head.next;

}

Complexity

  • ⏰ Time complexity: O(log(k) * n), k is number of list and n is number of total elements.
  • 🧺 Space complexity: O(k)

Method 2 - Using merge 2 lists solution sequentially

We have already solved Merge Two Sorted Lists.

Code

1
2
3
4
5
6
7

public ListNode mergeKLists(ListNode[] lists) {
    ListNode ans = new ListNode(Integer.MIN_VALUE);
    for(ListNode list : lists){
        ans = mergeTwoList(ans, list);
    }
    return ans.next;
}

Method 3 - Using merge 2 lists solution in a merge sort way

We have already solved Merge Two Sorted Linked Lists, that merges 2 sorted lists. We can also club Merge Sort Algorithm#Method 2 - Iterative or Bottom up Merge Sort.

So, we will keep on merging 2 lists at a time, till we have 1 list remaining.

So, initially we will have k/2 lists remaining, then k/4 and finally after some time 1 remaining. We take O(n) time to merging 2 sorted lists, finally we have time complexity of O(n * log k).

1
2

T(N) = 2 T(K/2) + N
T(N) = O (N log K)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

public ListNode mergeKLists(ListNode[] lists) {
	if (lists == null || lists.length == 0)
		return null;

	int k = lists.length;

	while(k>=1){
		// pick 1 list from start, another for end.
		for(int i = 0; i < k/2; i++){
			ListNode l1 = lists[i];
			ListNode l2 = lists[k-i-1];
			lists[i] = mergeTwoLists(l1, l2);
		}
		// we have to now process remaining k/2 list
		k = k /2;
	}

	return lists[0];
}
 
1
2
3
4
5
6
7
8
9

public ListNode mergeKLists(ListNode[] lists) {
	if(lists==null || lists.length==0) return null;
	
	for(int step = 1; step < lists.length; step <<= 1) {
		for(int i = 0; i < lists.length-step; i += 2*step)
			lists[i] = mergeTwoLists(lists[i], lists[i+step]);
	}
	return lists[0];
}

Complexity

  • ⏰ Time complexity: O(n log k)
  • 🧺 Space complexity: O(1)

Cons: Does in place modification.

Method 4 - Using Recursion and Divide and Conquer

This is similar to Merge Sort Algorithm#Method 1 - Recursive Top Down Merge Sort solution, resembling method 2’s iterative approach.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

public ListNode mergeKLists(ListNode[] lists) {
	int k = lists.length;
	if (k == 0) return null;
	
	return mergeKLists(lists, 0, k-1);
}

public ListNode mergeKLists(ListNode[] lists, int start, int end) {
	if (end - start == 0) return lists[start];
	if (end - start == 1) {
		return mergeLists(lists[start], lists[end]);
	}  
	
	int mid = start + ((end - start) / 2);
	ListNode listA = mergeKLists(lists, start, mid);
	ListNode listB = mergeKLists(lists, mid+1, end);
	
	return mergeTwoLists(listA, listB);
}

Complexity

  • ⏰ Time complexity: O(n log k)
  • 🧺 Space complexity: O(k)