Merge K Sorted Linked Lists
Merge K sorted linked lists.
Input: lists = [[2,2,3],[1,5]]
Output: [1,2,2,3,5]
Explanation: Extracts the smallest current node iteratively using a priority queue to build a single merged and sorted linked list.

Question

Merge K sorted linked lists.

Input: lists = [[2,2,3],[1,5]]

Output: [1,2,2,3,5]

Explanation: Extracts the smallest current node iteratively using a priority queue to build a single merged and sorted linked list.

Anonymous · Accepted Answer

import heapq

def solution(lists:List[Listnode]):

h=[]

from i, node in enumerate(lists):

heapq.heappush(h, (node.val, i, node)

dummy=Listnode()

current=dummy

while h:

smallval,i, smallestnode=heapq.heappop(h)

current.next=smallestnode

current=current.next

nextnode=current.next

if nextnode:

heapq.heappush(nextnode.val,i,nextnode)