# Merge k sorted linked lists and return it as one sorted list

**Problem statement**

Merge k sorted linked lists and return it as one sorted list.

**Solution**

We reduce the problem to the *merging of two linked lists* problem. This can be done in time and space. So we first write out the function to merge two sorted lists:

1 2 3 4 5 6 7 8 9 10 11 |
def merge(self, lst1, lst2): if lst1 == None: return lst2 if lst2 == None: return lst1 if lst1.val < lst2.val: lst1.next = self.merge(lst1.next, lst2) return lst1 else: lst2.next = self.merge(lst1, lst2.next) return lst2 |

We can then go on and iterate over all the lists and merge them in pairs. We will merge the first two lists and then merge the resulting list with the subsequent list in the array. The use that result and merge it with the next un visited list and so on.

**Full code**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
class ListNode(object): def __init__(self, x): self.val = x self.next = None def __str__(self): head = self ans = '' while head != None: ans = ans + str(head.val) head = head.next if head != None: ans = ans + '->' return ans class Solution(object): def merge(self, lst1, lst2): if lst1 == None: return lst2 if lst2 == None: return lst1 if lst1.val < lst2.val: lst1.next = self.merge(lst1.next, lst2) return lst1 else: lst2.next = self.merge(lst1, lst2.next) return lst2 def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode """ if len(lists) == 0: return None for i in range(0, len(lists) - 1): lists[i+1] = self.merge(lists[i], lists[i+1]) return lists[-1] def main(): head1 = ListNode(1) head1.next = ListNode(5) head1.next.next = ListNode(15) head2 = ListNode(-1) head2.next = ListNode(17) head2.next.next = ListNode(19) head3 = ListNode(1) head3.next = ListNode(18) head3.next.next = ListNode(100) head3.next.next.next = ListNode(200) solution = Solution() print(solution.mergeKLists([head1, head2, head3])) print(solution.mergeKLists([None])) print(solution.mergeKLists([None, ListNode(1)])) print(solution.mergeKLists([])) print(solution.mergeKLists([ListNode(1)])) if __name__ == "__main__": main() |