merge k sorted lists

🏠

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.

Solution

This problem is classified as hard, and it can absolutely be intimidating the first time you come across it, however you'll soon realise this is very simple and straight-forward wrangling of L values (L being the number of lists), and simple re-wiring.

An elegant solution to this problem involves working our way through the lists by using a current node (the red dot). Think of current as an electrician going through and doing some rewiring work:

 1 class ListNode(object):
 2     def __init__(self, x, n=None):
 3         self.val = x
 4         self.next = n
 5 
 6 def mergeKLists(A):
 7     dummy = node = ListNode(0)
 8     while A:
 9         A.sort(key = lambda x: x.val)
10         node.next = A[0]
11         node = node.next
12         if A[0].next:
13             A.append(A[0].next)
14         A.pop(0)
15     return dummy.next
16 
17 a = ListNode(3, ListNode(4, ListNode(9, ListNode(10))))
18 b = ListNode(2, ListNode(5, ListNode(8, ListNode(11))))
19 c = ListNode(1, ListNode(6, ListNode(7, ListNode(12))))
20 
21 head = mergeKLists([a, b, c])
22 while head:
23     print(head.val, end=' ')
24     head = head.next

Output:

1 1 2 3 4 5 6 7 8 9 10 11 12

Note

You'll also find a problem entitled "merge 2 sorted lists". The solution provided here can be used to solve this problem with only 2 lists.

Time and Space Complexity