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:
- 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
listby 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
- 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 11 node = node.next 12 if A.next: 13 A.append(A.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
1 1 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