# merge k sorted lists

🏠

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

## 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.
 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])

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