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:

• Adding the first nodes of linked-lists 1, 2 and 3 into a python list. This are the highlighted nodes in the video.
• Sorting this python list by value, in increasing order, so the smallest node is at the front.
• Assigning this smallest node to current.next, then assigning it to current. This is when the arrow changes, and the red dot progresses.
• Popping the smallest node out of our python list.
• Repeat while there are still nodes in the list.

 1class ListNode(object):
 2    def __init__(self, x, n=None):
 3        self.val = x
 4        self.next = n
 5
 6def 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
17a = ListNode(3, ListNode(4, ListNode(9, ListNode(10))))
18b = ListNode(2, ListNode(5, ListNode(8, ListNode(11))))
19c = ListNode(1, ListNode(6, ListNode(7, ListNode(12))))
20
21head = mergeKLists([a, b, c])
22while head:
23    print(head.val, end=' ')
24    head = head.next

Output:

11 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

$$time = O(n)$$ $$space = O(1)$$