Merge k Sorted Lists

You are given k sorted linked lists; merge them into a single sorted list. The naive approach — concatenate everything and sort — is O(n log n) where n is the total number of nodes, and it throws away the ordering information the lists already have.

The key insight: at any moment, the next smallest node overall must be one of the k current heads. Put all heads in a min-heap keyed by node value, and the machine can pop the true minimum in O(log k), append it to the result, and push its next successor back. Each node enters and leaves the heap exactly once.

Approach in steps:

1. Push the head of every non-empty list into a min-heap.
2. Pop the minimum, append it to the merged tail, and push popped.next if it exists.
3. Repeat until the heap is empty.

import heapq
from itertools import count
 
def mergeKLists(lists):
    uid = count()
    heap = [(lst.val, next(uid), lst) for lst in lists if lst]
    heapq.heapify(heap)
    dummy = tail = ListNode()
    while heap:
        _, _, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, next(uid), node.next))
    return dummy.next

Time is O(n log k) with k lists and n total nodes; space is O(k) for the heap. This beats O(n log n) whenever k is meaningfully smaller than n.

Trickiest edge case: comparing nodes directly fails because linked list nodes have no __lt__. Storing a unique index per entry makes heap comparisons unambiguous. Also handle empty lists up front — a heap of all-empty heads leaves nothing to merge, and you must return None without touching a nonexistent node.