Merging k sorted linked lists into a single sorted list is widely considered the most important linked list problem for interviews. It combines pointer manipulation with algorithmic thinking, and interviewers use it to gauge whether you can move beyond brute force toward optimal data structure choices.

The problem is straightforward to state: given k linked lists, each individually sorted in ascending order, merge all of them into one sorted linked list and return its head.

The Brute Force Approach

The simplest strategy is to merge lists one pair at a time. Start with the first list, merge it with the second, take the result and merge it with the third, and so on. Each pairwise merge takes O(n) where n is the combined length of the two lists. If you have k lists with a total of n nodes across all of them, the first merge processes some nodes, the second merge processes a growing intermediate list plus the next list, and so on. The total work is O(nk) because the intermediate result grows with each merge and you repeat the process k - 1 times.

For small k this is acceptable, but when k is large - say 10,000 sorted streams - the repeated reprocessing of the growing intermediate list becomes a bottleneck.

Optimal: Min-Heap of Size k

The key insight is that at any moment, the next node in the merged result must be the smallest among the current heads of all k lists. Instead of scanning all k heads each time (which would also give O(nk)), you maintain a min-heap of size k that always gives you the smallest head in O(log k) time.

The algorithm works as follows:

1. Push the head node of each non-empty list into a min-heap
2. Pop the smallest node from the heap - this is the next node in the result
3. If that node has a next pointer, push its next node into the heap
4. Repeat until the heap is empty

Step through how nodes are added to and popped from the heap as two linked lists are merged:

The tuple (val, i, node) deserves explanation. Python's heapq compares tuples element by element. If two nodes have the same value, Python would try to compare the nodes themselves, which fails because ListNode objects are not comparable. The index i serves as a tiebreaker - it is unique per list, so Python never reaches the node comparison.

Time and Space Complexity

Each of the n total nodes is pushed into and popped from the heap exactly once. Each push and pop is O(log k) because the heap never exceeds size k. Total time: O(n log k). Space: O(k) for the heap.

Compare this to the brute force O(nk). When k = 10,000 and n = 1,000,000, the heap approach does roughly 1,000,000 * 14 = 14 million operations versus 10 billion for brute force. That is a 700x improvement.

Divide and Conquer Alternative

There is a second O(n log k) approach that avoids a heap entirely. Pair up the k lists and merge each pair. This reduces k lists to k/2 lists. Repeat: merge pairs again to get k/4 lists. Continue until one list remains. This is exactly the merge-sort pattern applied to lists instead of arrays.

See how nodes are reversed in groups of k and reconnected:

There are log k rounds, and each round processes all n nodes exactly once. Total: O(n log k), same as the heap approach. The divide and conquer version uses O(1) extra space (no heap), but the heap version is often simpler to implement correctly under interview pressure.