Tags:

• Medium
• heap

23. Merge k Sorted Lists

link

Time complexity: O(n log k) (that more than k elements in the heap)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:

        n = len(lists)


        dummy = ListNode(-1)

        heap = []

        for i, node in enumerate(lists):
            if node:
                heappush(heap, (node.val, i))


        end = dummy
        
        while heap:
            _, idx = heappop(heap)

            end.next = lists[idx]

            lists[idx] = lists[idx].next

            if lists[idx]:
                heappush(heap,(lists[idx].val, idx))

            end = end.next

        end.next = None

        return dummy.next