Merge K Sorted Linked Lists
- 2 min read
- LC-Medium
3 years ago
Solution
- Successor of Merge Two Sorted Lists
- Naive solution is to merge a list one at a time, i.e. merge the first two lists first, then merge this one with the third list, etc...
- This leads to a time complexity of O(n^2)
- Better solution is to merge two linked lists at a time, i.e. first two, next two. So if you have 8 lists at first, next iteration it becomes 4, next iteration it becomes 2.
- Since the size of our lists is getting halved each time, the overall time complexity of this algorithm would come down to be O(n log k)
| Time | Space | Explanation |
|---|---|---|
O(n log k) | O(1) |
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if len(lists) == 0:
return None
while len(lists) > 1:
merged_lists = []
for i in range(0, len(lists), 2):
l1 = lists[i]
l2 = lists[i + 1] if (i + 1) < len(lists) else None
merged_list = self.merge_lists(l1, l2)
merged_lists.append(merged_list)
lists = merged_lists
return lists[0]
def merge_lists(self, l1, l2):
l3 = dummy = ListNode()
next_val = None
while l1 and l2:
if l1.val < l2.val:
next_val = l1.val
l1 = l1.next
else:
next_val = l2.val
l2 = l2.next
l3.next = ListNode(next_val)
l3 = l3.next
if l1:
l3.next = l1
if l2:
l3.next = l2
return dummy.next