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.


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:

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


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


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