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

```
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