Solution: Merge K Sorted Lists

Let's solve the Merge K Sorted Lists problem with the K-way Merge pattern.

We'll cover the following

Statement#

Given an array of kk sorted linked lists, your task is to merge them into a single sorted linked list and return the head of this linked list.

Constraints:

  • k=k = lists.length
  • 0≤k≤1030 \leq k \leq 10^3
  • 0≤0 \leq lists[i].length ≤500\leq 500
  • −103≤-10^3 \leq lists[i][j] ≤103\leq 10^3
  • Each lists[i] is sorted in ascending order.
  • The sum of all lists[i].length will not exceed 10310^3.

Solution#

Since our task involves multiple lists, we can use the divide and conquer technique, starting with pairing the lists and then merging each pair. We repeat this until all the given lists are merged. This way, after the first pairing, we’re left with k2\frac{k}{2} lists, then k4\frac{k}{4}, k8\frac{k}{8} and so on.

List 2
List 2
List 0
List 0
List 0
List 0
List 2
List 2
List 3
List 3
List 1
List 1
List 0
List 0Viewer does not support full SVG 1.1

We have access to two pointers, each pointing to a different list. Let’s call them head1 for the first list and head2 for the second list. If the node value of head1 is less than or equal to the node value of head2, add the head1 node to the new merged list. Otherwise, add the head2 node.

Created with Fabric.js 3.6.6 head1 head2 11 21 prev 41 51 23 42 dummy Initial setuphead1 and head2 point to two different lists, and prev points to a dummy node.

1 of 8

Created with Fabric.js 3.6.6 head1 head2 11 21 prev 41 23 51 42 dummy Since head1's value < head2's value, we'll add 11 to the merged list.head1 will point to the next node.

2 of 8

Created with Fabric.js 3.6.6 head1 head2 41 21 dummy 51 23 prev 42 11 Since head2's value < head1's value, we'll add 21 to the merged list.head2 will point to the next node.

3 of 8

Created with Fabric.js 3.6.6 head1 head2 41 23 dummy 51 42 prev 11 21 Since head2's value < head1's value, we'll add 23 to the merged list.head2 will point to the next node.

4 of 8

Created with Fabric.js 3.6.6 head1 head2 41 42 dummy 51 prev 11 21 23 Since head1's value < head2's value, we'll add 41 to the merged list.head1 will point to the next node.

5 of 8

Created with Fabric.js 3.6.6 head1 head2 51 42 dummy 11 21 23 41 prev Since head2's value < head1's value, we'll add 42 to the merged list.head2 will now point to NULL.

6 of 8

Created with Fabric.js 3.6.6 NULL head1 head2 51 dummy 11 21 23 41 42 prev Since head2 has become NULL, we'll add the remaining elements inthe first list to the dummy list.

7 of 8

Created with Fabric.js 3.6.6 Both lists have been merged into one list. NULL head1 head2 dummy 11 21 23 41 42 51 prev NULL

8 of 8

Let’s look at the code for the solution below:

main.py
print_list.py
linked_list.py
linked_list_node.py
Merge K Sorted Lists

Time complexity#

The time complexity is O(nlog⁡k)O(n \log k), where kk is the number of the lists and nn is the total number of elements across all lists.

Space complexity#

The space complexity is O(1)O(1), since constant space was utilized.

Merge K Sorted Lists

Final Remarks