23 - heap

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:

        h = [(node.val, random.random(), node) for node in lists if node]
        heapq.heapify(h)
        head = None
        tail = None
        while h:
            _, _, node = heapq.heappop(h)
            if head:
                tail.next = node
                tail = tail.next
            else:
                head = node
                tail = node
            if node.next:
                heapq.heappush(h, (node.next.val, random.random(), node.next))

        return head