Merge k Sorted Lists LeetCode solution in Python

1
# Definition for singly-linked list.
2
# class ListNode:
3
#     def __init__(self, val=0, next=None):
4
#         self.val = val
5
#         self.next = next
6
from heapq import heappush, heappop
7

8

9
class Solution:
10
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
11
        heap = []
12
        heapq.heapify(heap)
13
        start = end = ListNode(-1)
14
        for i in lists:
15
            if i:
16
                heappush(heap, (i.val, id(i), i))
17
        while heap:
18
            val, iD, node = heappop(heap)
19
            end.next = node
20
            node = node.next
21
            end = end.next
22
            if node:
23
                heappush(heap, (node.val, id(node), node))
24

25
        return start.next