This problem follows the Divide and Conquer / Heap pattern, commonly found in the Linked List category. Recognizing this pattern is key to solving it efficiently in an interview setting.
Use a min-heap to always pick the smallest head. Or merge lists pairwise.
The heap always has at most k elements (one per list), so each push/pop is O(log k) — total is O(n log k) for all n nodes.
heap = []
for i, l in enumerate(lists):
if l: heappush(heap, (l.val, i, l))
dummy = ListNode(0)
curr = dummy
while heap:
val, i, node = heappop(heap)
curr.next = node
curr = curr.next
if node.next:
heappush(heap, (node.next.val, i, node.next))
return dummy.nextPractice Merge K Sorted Lists and similar Linked List problems with flashcards. Build pattern recognition through active recall.
Practice this problem