Merge k sorted link lists in python
Bug in Solution3  (using heapq)

The items being put on the heap need to be fully sortable.  Tuples are compared element by element. If the first element of two tuples compare equal, then the next element of the two tuples are compared.  In your solution, the second element of the tuple is a ListNode.  But no methods for comparing ListNodes have been defined.  So if the first element of the tuples are equal a TypeError will be raised when the ListNodes are compared.  The solution is to use 3-tuples: (value, seq_no, ListNode), in which the seq_nos are unique.

class Solution3:
    # @param a list of ListNode
    # @return a ListNode
    def mergeKLists(self, lists):
        dummy = ListNode(0)
        current = dummy

        heap = []
        for seq_no, sorted_list in enumerate(lists):
            if sorted_list:
                heapq.heappush(heap, (sorted_list.val, seq_no, sorted_list))

        while heap:
            _, seq_no, smallest = heapq.heappop(heap)
            current.next = smallest
            current = current.next
            if smallest.next:
                heapq.heappush(heap, (smallest.next.val, seq_no, smallest.next))

        return dummy.next


See discussion in heapq documentation: https://docs.python.org/3.7/library/heapq.html#priority-queue-implementation-notes