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 head2if not head2:
return head1root = 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.nextreturn root`
and then merge through the array
def merge_lists(lists):
if len(lists) < 1:
return listscur = lists[0]
for i in lists[1:]:
cur = merge_two(cur, i)return cur