Merge k Sorted Lists

Core idea: Merging two sorted lists is easy and costs only their combined length. So don't merge the k lists one-by-one into a growing accumulator — pair them up and merge pairs, halving the number of lists every round. After log k rounds you're down to one list, and each element rode through only log k merges instead of k.

Problem, rephrased

Forget the textbook phrasing. Here's the scenario:

You run a logging pipeline. k machines each emit a stream of events already sorted by timestamp — within one machine, events come out in order, but the machines are independent. You want a single global timeline: one sorted sequence containing every event from all machines, still in timestamp order.

Each machine's stream is a sorted singly-linked list of timestamps. You're handed an array lists of their head pointers and must return the head of one merged sorted list. Let N be the total number of nodes across all k lists.

The lists arrive as linked lists, not arrays — so "look at the next smallest element" means following .next pointers, and we build the result by splicing nodes, not by copying values.