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 . . . Read more