The tell: k sorted sequences to merge, with total length n.
How you get there
1A heap holds one candidate from each list, so the next smallest is always available.
2Each of the n extractions costs log k, giving O(n log k).
3Push a counter as a tiebreaker, since ListNode objects are not orderable.
Solution
Python
import heapq
def merge_k_lists(lists):
heap: list[tuple] = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node)) # i breaks ties
dummy = tail = ListNode()
while heap:
_, i, node = heapq.heappop(heap)
tail.next = node
tail = node
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
Time
O(n log k)
Space
O(k)
What goes wrong
Pushing (val, node) raises TypeError on equal values, because Python then compares the nodes.