Leetcode 23. Merge k Sorted Lists

Let's understand what we're being asked to do. We have k linked lists, where each list is already sorted in ascending order, and we need to merge them into one sorted linked list.

For example, if we have three lists: [1→4→5], [1→3→4], and [2→6], we need to combine them into a single sorted list: [1→1→2→3→4→4→5→6].

Tracing through: we need to repeatedly pick the smallest node among all the current heads of the k lists. Initially, the heads are 1, 1, and 2 - we pick 1 (from list 1), then the heads become 4, 1, 2 - we pick 1 (from list 2), and so on.

Important constraint: Each individual list is already sorted, so we don't need to sort within lists - we only need to merge them efficiently.

Edge cases to consider: What if some lists are empty? What if k=0 (no lists at all)? What if all lists have only one node? What if one list is much longer than the others?

The straightforward approach is to repeatedly scan through all k list heads to find the minimum value node. Pick that node, add it to the result list, and advance that list's pointer. Repeat until all lists are exhausted. This approach is simple to understand but requires O(k) comparisons for each of the n total nodes, where n is the sum of all list lengths.

At each step, we need to find the smallest value among the current heads of all k lists. Once we pick that smallest node, we advance that list's pointer to the next node.

This creates a pattern: we're repeatedly asking 'what's the minimum among these k candidates?' and then updating one candidate.

If we scan through all k list heads every time to find the minimum, that's O(k) per node. With n total nodes across all lists, this gives us O(n*k) time.

But there's a data structure designed specifically for efficiently tracking and extracting the minimum from a changing set of values - this can reduce our per-node work from O(k) to O(log k)!

Imagine you're a teacher merging k sorted stacks of graded papers (each stack sorted by score). You want to create one final sorted stack.

You look at the top paper from each of the k stacks, pick the one with the lowest score, and place it on your result pile. Then you look at the tops again (one stack now has a new top paper).

Instead of scanning all k stacks every time, you could organize them so you always know which stack has the current minimum top paper. When you take that paper, you update just that one stack's position. This 'organized tracking' is exactly what makes the merge efficient.

The optimal approach uses a min-heap (priority queue) to efficiently track the smallest head among all k lists. Initialize the heap with the first node from each non-empty list. Repeatedly extract the minimum node from the heap, add it to the result, and if that node has a next node, insert the next node into the heap. This reduces the per-node work from O(k) to O(log k), achieving O(n log k) overall time complexity.

import heapq
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def merge_k_lists(lists):
    """
    Merge k sorted linked lists using a min-heap.
    Time: O(n log k), Space: O(k)
    """
    # Initialize min-heap with first node from each list
    min_heap = []
    
    for i, head in enumerate(lists):
        if head:
            heapq.heappush(min_heap, (head.val, i, head))
    
    # Create dummy head for result list
    dummy = ListNode(0)
    current = dummy
    
    # Process nodes from heap
    while min_heap:
        val, list_idx, node = heapq.heappop(min_heap)
        
        # Add node to result
        current.next = node
        current = current.next
        
        # If node has next, add to heap
        if node.next:
            heapq.heappush(min_heap, (node.next.val, list_idx, node.next))
    
    return dummy.next

• Min-heap for k-way merge: When merging multiple sorted sequences, use a min-heap of size k to always extract the smallest element across all lists - this avoids comparing all k elements repeatedly and reduces comparisons from O(k) to O(log k) per element.
• Custom comparator for complex objects: Store entire ListNode objects in the heap with a custom comparator that compares node values, not just primitive values - this eliminates the need to track which list each value came from since the node itself maintains the next pointer.
• Lazy population strategy: Only add the head of each list initially to the heap, then add the next node from a list only when its current node is extracted - this keeps heap size at O(k) instead of O(n) where n is total nodes, minimizing memory and maintaining efficiency.
• Null pointer handling in heap operations: Always check if node.next exists before adding to heap after extraction - adding null nodes causes runtime errors and is a common mistake when the heap automatically tries to compare null values.
• Time complexity advantage: This heap approach achieves O(N log k) where N is total nodes and k is number of lists, which dramatically outperforms the naive O(Nk) approach of repeatedly scanning all list heads, especially when k is large.
• Multi-source streaming pattern: This technique extends beyond linked lists to any scenario where you need to merge multiple sorted streams (log files, database query results, real-time data feeds) - the heap ensures you always process the globally smallest unprocessed element efficiently.