educative.io

Educative

The solution demonstrated is not optimal

I feel the solution implemented is more complicated than needed,
The question mentions the k linked lists are already sorted. There is no need to use a heap and re-sort it
Instead use the logic of merging two sorted lists like in merge-sort and solve the problem in O(N) instead of O(NLogN)

I implemented merge_twol(l1,l2)

def merge_two(head1, head2):

if not head1:
return head2

if not head2:
return head1

root = None
cur = None
while head1 and head2:
nn = None
if head1.value < head2.value:
nn = head1
head1 = head1.next
else:
nn = head2
head2 = head2.next
if cur:
cur.next = nn
cur = cur.next
else:
cur = nn
root = nn
while head1:
cur.next = head1
head1 = head1.next
cur = cur.next
while head2:
cur.next = head2
cur = head2
head2 = head2.next

return root`

and then merge through the array

def merge_lists(lists):

if len(lists) < 1:
return lists

cur = lists[0]
for i in lists[1:]:
cur = merge_two(cur, i)

return cur

1 Like

Hi Muaz! I think your solution is O(N * K), which is obviously worse than the proposed O(N * LogK). This is because after the first merge, you have to loop over the first result again for the next merge. For example, if you have 4 lists with these lengths: 1000, 1, 1, 1, you will have:

  • the first merge in 1001 steps,
  • the second merge in 2002 steps,
  • and the third merge in 3003 steps
1 Like