Problem Description
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.
Example 1:
- Input:
lists = [[1,4,5],[1,3,4],[2,6]] - Output:
[1,1,2,3,4,4,5,6]
Example 2:
- Input:
[] - Output:
[]
My Idea
My initial idea was to simply iterate over the list and merge the elements one by one. This yielded a time complexity of O(n*k). To optimize this approach we can go ahead and merge the list in twos until we get one list. This way in every iteration the amount of lists to be merged is 2 times less. This yields a time complexity of O(n*log(k)).
My solution
from typing_extensions import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Time Complexity O(n*log(k))
def mergeKLists(lists: list(Optional[ListNode]))->Optional[ListNode]:
def mergeTwoLists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if not list1:
return list2
if not list2:
return list1
res = ListNode()
curr = res
while list1 and list2:
if list1.val <= list2.val:
curr.next = list1
list1 = list1.next
else:
curr.next = list2
list2 = list2.next
curr=curr.next
if list1:
curr.next = list1
if list2:
curr.next = list2
return res.next
if not lists or len(lists)==0:
return None
while len(lists) > 1:
tempList = []
for i in range(0,len(lists),2):
l1 = lists[i]
l2 = lists[i+1] if (i+1)<len(lists) else None
tempList.append(mergeTwoLists(l1,l2))
lists = tempList
return lists[0]
# Time Complexity O(n*k)
def mergeKListsInitial(lists: list(Optional[ListNode]))->Optional[ListNode]:
def mergeTwoLists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if not list1:
return list2
if not list2:
return list1
res = ListNode()
curr = res
while list1 and list2:
if list1.val <= list2.val:
curr.next = list1
list1 = list1.next
else:
curr.next = list2
list2 = list2.next
curr=curr.next
if list1:
curr.next = list1
if list2:
curr.next = list2
return res.next
if len(lists)==0:
return None
elif len(lists)==1:
return lists[0]
else:
res = ListNode(0)
res.next=mergeTwoLists(lists[0],lists[1])
if len(lists)>2:
for i in range(2,len(lists)):
res.next=mergeTwoLists(res.next,lists[i])
return res.next