merge k sorted lists

Go Back home
1 [
2   1->4->5,
3   1->3->4,
4   2->6
5 ]
 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(1, ListNode(4, ListNode(5)))
18 b = ListNode(1, ListNode(3, ListNode(4)))
19 c = ListNode(2, ListNode(6))
20 
21 head = mergeKLists([a, b, c])
22 while head:
23     print(head.val, end=' ')
24     head = head.next

Output:

1 1 1 2 3 4 4 5 6

paste-d2257755660905dd68444fa9afe4e7e5efa426bc.mp4

See also

merge 2 sorted lists