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

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