# 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)

root = None
cur = None
nn = None
else:
if cur:
cur.next = nn
cur = cur.next
else:
cur = nn
root = nn
cur = cur.next

return root`

and then merge through the array

``````def merge_lists(lists):
``````

if len(lists) < 1:
return lists

cur = lists
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