Merge K Sorted Lists Algorithm Solution

The merge k sorted lists problem requires combining multiple sorted linked lists into a single sorted linked list. This classic DSA problem demonstrates effective use of heap-based data structures and recursive divide-and-conquer strategies for optimal performance.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. What is the maximum number of lists we might receive? (e.g., are we dealing with small fixed-size inputs or potentially thousands of lists?)
2. Are the input lists guaranteed to be sorted in ascending order, or could they be descending?
3. Can we modify the input lists during processing, or must we preserve them?
4. What is the expected size of each individual list? (e.g., small lists vs. very large lists)
5. Should we return a new merged list or can we mutate one of the existing lists?

Restatement of the pattern: The problem involves merging multiple sorted linked lists into a single sorted linked list. This is a classic "merge" operation extended to k lists rather than just two.

Signal words and constraint shape:

• "Merge" or "combine" multiple sorted collections
• Input consists of several pre-sorted arrays or lists
• Each list is individually sorted in ascending order
• Expected output is a single sorted array/list
• Often involves "k" lists where k ≥ 2

Assumptions:

• All input lists are sorted in ascending order
• Lists may have different lengths
• We can use additional space for the result (no requirement to mutate inputs)
• The solution should produce a valid sorted list as output

Pattern suitability: This pattern is best suited for static scenarios where all inputs are available upfront. It's not ideal for streaming data where lists arrive one-by-one over time, though a similar approach could be adapted for online processing using priority queues that maintain the current minimum across all active lists.

The pattern is a canonical example of "divide and conquer" or "merge-based" approaches, where we leverage the fact that individual lists are already sorted to build an efficient overall solution rather than sorting everything from scratch.

2. When to Use This Pattern

Signal words and constraint shapes:

• "K sorted lists" or "multiple sorted arrays"
• "Merge into one sorted list"
• Lists of different lengths
• "K pointers" or "K-way merge"
• "Sorted input" or "pre-sorted data"

Why this pattern fits better than alternatives: This pattern is specifically designed for merging multiple pre-sorted sequences efficiently. Compared to naive approaches like concatenating and sorting (O(N log N)), or pairwise merging (O(N²)), the K-way merge using a min-heap achieves optimal O(N log K) time complexity where N is the total number of elements and K is the number of lists.

Conditions where variations apply:

• For two sorted lists, a simple two-pointer approach is more efficient (O(N) time)
• For streaming data with new elements arriving, a priority queue-based streaming merge would be preferred
• If lists are nearly identical in size and can be processed in batches, divide-and-conquer might offer better cache locality

Core insight that makes this pattern work: The key insight is that we don't need to compare all elements at once. Instead, we can maintain a min-heap of size K containing the smallest unprocessed element from each list. At each step, we extract the minimum and add the next element from that same list to the heap. This ensures we always process elements in sorted order while maintaining optimal time complexity.

The pattern works because:

1. We can efficiently find the next smallest element among K candidates
2. Each list is already sorted, so we only need to advance pointers within lists
3. The heap maintains the invariant that we always have access to the smallest available element

3. Approach Evolution

Interview communication script:

"My first instinct is to use a brute force approach where I collect all elements from all lists and then sort them, because that's straightforward and guaranteed to work. But that's O(n log n) time where n is the total number of elements, and it requires O(n) extra space to store all elements. That's not optimal.

Let me think about how to optimize this. I notice that all lists are already sorted, so I don't need to sort everything from scratch. Instead of collecting all elements, I can use a min-heap to keep track of the smallest element from each list at any time. This way, I can extract the minimum element one by one and add the next element from the same list.

I notice that if I maintain a min-heap of size k (where k is the number of lists), I can reduce the time complexity to O(n log k) where n is the total number of elements. Each heap operation takes O(log k) time, and I perform n such operations.

The key insight is that instead of sorting all elements, I can merge the lists incrementally by always selecting the smallest available element from the k lists. This is essentially the merge step in merge sort, but generalized to k lists rather than 2."

Brute-force approach and why it is not ideal: The brute force approach collects all elements from all k lists into one array, then sorts the entire array. This works but is inefficient because:

• Time complexity: O(n log n) where n is total elements
• Space complexity: O(n) for storing all elements
• Doesn't leverage the fact that each list is already sorted

Improved approach and the key optimization: Use a min-heap (priority queue) to maintain the smallest elements from each list:

• Initialize heap with first element of each list
• Extract minimum element and add next element from same list to heap
• This leverages the sorted property of input lists to avoid full sorting

Final approach with step-by-step reasoning:

1. Create a min-heap that stores nodes (value, list index, element index)
2. Initialize heap with first element from each of the k lists
3. While heap is not empty:
   • Extract minimum element from heap
   • Add it to result list
   • If there's a next element in same list, add it to heap
4. Return merged result list

Important invariants that must hold:

• Heap always contains at most k elements (one from each list)
• At any point, heap top is the smallest among all available elements
• Each list's elements are processed in order (maintaining sorted property)
• No element is processed more than once

4. Data Structure Choice

For the merge K sorted lists problem, I'll use a min-heap (PriorityQueue) as my primary data structure.

Primary Data Structures Used

1. Min-Heap (PriorityQueue) - The core data structure that allows us to efficiently retrieve the smallest element across all lists
2. ListNode - Standard linked list node structure to represent elements in the merged result

Why Each Data Structure Is Needed

The min-heap is essential because:

• It maintains elements in sorted order automatically
• It provides O(log k) insertion and extraction operations where k is the number of lists
• It allows us to efficiently track the next smallest element across all currently available elements from different lists

The ListNode structure is needed because:

• It's the required output format for the merged linked list
• It allows us to build the result incrementally by linking nodes together

Time and Space Impact

Min-Heap:

• Time: O(log k) for insertions/extractions, O(k) to initialize with first elements
• Space: O(k) for storing at most one element from each list

ListNode:

• Time: O(1) per node creation
• Space: O(n) where n is the total number of elements across all lists

Helper Structure for Simplification

I'll use a custom wrapper class ListNodeWithListIndex that pairs each ListNode with its originating list index. This simplifies tracking which list each element came from and makes it easy to advance the corresponding list pointer when we extract an element.

This approach avoids storing entire lists in memory and instead only keeps track of one element per list at any given time, making it both time and space efficient.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to demonstrate how it works step by step.

Example: lists = [[1,4,5],[1,3,4],[2,6]]

Step 1: Initialize min-heap with first elements from each list

• Heap contains: (1,0,0), (1,1,0), (2,2,0)
• Where each tuple is (value, listIndex, elementIndex)
• Heap: [1,1,2] - smallest value 1 is at top

Step 2: Extract minimum and add to result

• Pop (1,0,0): value=1, listIndex=0, elementIndex=0
• Result: [1]
• Add next element from same list to heap: (4,0,1)
• Heap now: [1,2,4]

Step 3: Continue extracting minimums

• Pop (1,1,0): value=1, listIndex=1, elementIndex=0
• Result: [1,1]
• Add next element from list 1: (3,1,1)
• Heap now: [2,3,4]

Step 4: Continue process

• Pop (2,2,0): value=2, listIndex=2, elementIndex=0
• Result: [1,1,2]
• Add next element from list 2: (6,2,1)
• Heap now: [3,4,6]

Step 5: Continue until all elements processed

• Pop (3,1,1): value=3, listIndex=1, elementIndex=1
• Result: [1,1,2,3]
• Add next element from list 1: (4,1,2)
• Heap now: [4,4,6]

Step 6: Final steps

• Pop (4,0,1): value=4, listIndex=0, elementIndex=1
• Result: [1,1,2,3,4]
• Add next element from list 0: (5,0,2)
• Heap now: [4,5,6]

Step 7: Continue until heap is empty

• Pop (4,1,2): value=4, listIndex=1, elementIndex=2
• Result: [1,1,2,3,4,4]
• Add next element from list 1: (None - end of list)
• Heap now: [5,6]

Step 8: Final elements

• Pop (5,0,2): value=5, listIndex=0, elementIndex=2
• Result: [1,1,2,3,4,4,5]
• Add next element from list 0: (None - end of list)
• Heap now: [6]

Step 9: Final element

• Pop (6,2,1): value=6, listIndex=2, elementIndex=1
• Result: [1,1,2,3,4,4,5,6]
• Heap is now empty

Edge case handling:

• If any list is empty, we skip it during initialization
• If lists is null or empty, we return null
• When a list is exhausted, we don't add anything to heap from that list

The algorithm terminates correctly because:

1. We always extract the smallest available element
2. We maintain heap property throughout
3. Each list is processed sequentially, never skipping elements
4. When a list is exhausted, we don't add more elements from it
5. The heap ensures we always get the next smallest element in O(log k) time

6. Java Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // Handle edge cases
        if (lists == null || lists.length == 0) {
            return null;
        }
        
        // Use a min-heap to efficiently get the smallest element across all lists
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
        
        // Add the first node of each non-null list to the heap
        for (ListNode list : lists) {
            if (list != null) {
                minHeap.offer(list);
            }
        }
        
        // Create a dummy head to simplify list construction
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        
        // Process nodes from the heap until it's empty
        while (!minHeap.isEmpty()) {
            // Get the smallest node from the heap
            ListNode smallest = minHeap.poll();
            
            // Add it to our merged list
            current.next = smallest;
            current = current.next;
            
            // If there's a next node in the same list, add it to the heap
            if (smallest.next != null) {
                minHeap.offer(smallest.next);
            }
        }
        
        // Return the merged list (skip the dummy head)
        return dummy.next;
    }
}

This solution uses a min-heap to efficiently merge k sorted linked lists. The key insight is that we can maintain the smallest elements from each list in a priority queue, allowing us to always pick the next smallest element in O(log k) time where k is the number of lists.

7. Complexity Analysis

Time Complexity: O(N log k) where N is the total number of elements across all lists and k is the number of lists.

• The heap operations (insertion and extraction) take O(log k) time
• We perform these operations exactly N times (once for each element)
• Therefore, the overall time complexity is O(N log k)

Space Complexity: O(k) for the priority queue that stores at most one element from each list.

• The priority queue maintains at most k elements at any time
• We don't store all N elements, only one element per list in the heap
• The output array of size N is not counted in space complexity as it's required for the result

Why these bounds are correct:

The analysis assumes that we're using a min-heap to track the smallest elements from each list. Each of the N elements is processed exactly once, and for each element, we perform O(log k) heap operations. Since we never store more than k elements in the heap simultaneously, the space complexity remains O(k).

Optimality:

This is optimal for the given constraints. We must process each of the N elements at least once, and we cannot avoid the O(log k) cost of maintaining the heap structure. Any approach that processes elements in sorted order will require at least O(N log k) time, making this solution near-optimal for the problem constraints.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty input list: Handle gracefully when lists is null or empty - return null or empty result
• Single list: When only one list exists in the input, the algorithm should work correctly without unnecessary operations
• Empty lists within input: Lists that are themselves empty (but not null) should be handled without affecting the merge process

Duplicate Values and Repeated States

• Duplicate elements across lists: The solution must properly handle duplicate values, ensuring they appear in the correct order in the merged result
• Identical lists: When multiple lists are identical, the merge should correctly include all elements in sorted order

Boundary Conditions

• Null list elements: Input lists can contain null elements, which should be handled appropriately (though typically this wouldn't occur in valid test cases)
• Large input size: With up to 10⁴ lists and 5 × 10⁴ elements total, performance matters - avoid O(n²) solutions
• Single element lists: Lists with just one element should merge correctly without issues

Common Implementation Mistakes

• Incorrect heap initialization: Failing to properly initialize the priority queue with custom comparator or missing null checks
• Not handling null list elements: Accessing list.next without checking if list is null can cause NullPointerException
• Wrong comparator logic: Using incorrect comparison in the priority queue that leads to wrong ordering or infinite loops
• Memory leaks: Not properly managing references in the priority queue that could cause memory issues with large inputs
• Missing edge case handling: Forgetting to handle the case where input lists are empty or null, leading to runtime exceptions

// Example of proper null checking:
if (list != null && list.val != null) {
    // Process list
}

9. Alternative Approaches

There are several alternative approaches to solving the merge k sorted lists problem, each with different trade-offs:

Approach 1: Sequential Merging Instead of using a priority queue, we can merge lists sequentially. We start with the first list and iteratively merge it with each subsequent list. This approach has time complexity O(N×k) where N is the total number of elements and k is the number of lists. While simpler to implement, it's less efficient than the heap-based approach.

Approach 2: Divide and Conquer We can use a divide-and-conquer strategy where we recursively merge pairs of lists until we have one merged list. This approach has the same time complexity as the heap-based solution O(N log k) but with potentially better cache performance due to fewer operations. The space complexity is O(log k) due to recursion stack.

Approach 3: Flatten and Sort We can collect all elements from all lists into a single array, sort it, and then convert back to a linked list. This is O(N log N) time complexity but uses O(N) extra space for the temporary array. This approach is simpler to implement but less efficient than the optimal O(N log k) solution.

The heap-based approach is preferred because it maintains the optimal time complexity while being more intuitive than divide-and-conquer and more efficient than sequential merging or flattening approaches. The heap approach also naturally handles the case where lists are of different sizes, making it more robust in practice.

10. Test Cases

// Test case 1: Basic functionality with multiple lists
// Input: [[1,4,5],[1,3,4],[2,6]]
// Expected: [1,1,2,3,4,4,5,6]
@Test
public void testBasicMerge() {
    ListNode[] lists = new ListNode[3];
    lists[0] = new ListNode(1, new ListNode(4, new ListNode(5)));
    lists[1] = new ListNode(1, new ListNode(3, new ListNode(4)));
    lists[2] = new ListNode(2, new ListNode(6));
    
    ListNode result = mergeKLists(lists);
    assertLinkedListEquals(new int[]{1,1,2,3,4,4,5,6}, result);
}

// Test case 2: Empty lists
// Input: [[],[],[]]
// Expected: []
@Test
public void testEmptyLists() {
    ListNode[] lists = new ListNode[3];
    lists[0] = null;
    lists[1] = null;
    lists[2] = null;
    
    ListNode result = mergeKLists(lists);
    assertNull(result);
}

// Test case 3: One empty list and one non-empty
// Input: [[], [1,2,3]]
// Expected: [1,2,3]
@Test
public void testMixedEmpty() {
    ListNode[] lists = new ListNode[2];
    lists[0] = null;
    lists[1] = new ListNode(1, new ListNode(2, new ListNode(3)));
    
    ListNode result = mergeKLists(lists);
    assertLinkedListEquals(new int[]{1,2,3}, result);
}

// Test case 4: Single list
// Input: [[1,2,3]]
// Expected: [1,2,3]
@Test
public void testSingleList() {
    ListNode[] lists = new ListNode[1];
    lists[0] = new ListNode(1, new ListNode(2, new ListNode(3)));
    
    ListNode result = mergeKLists(lists);
    assertLinkedListEquals(new int[]{1,2,3}, result);
}

// Test case 5: Lists with duplicates
// Input: [[1,1,2], [1,3,3]]
// Expected: [1,1,1,2,3,3]
@Test
public void testDuplicateValues() {
    ListNode[] lists = new ListNode[2];
    lists[0] = new ListNode(1, new ListNode(1, new ListNode(2)));
    lists[1] = new ListNode(1, new ListNode(3, new ListNode(3)));
    
    ListNode result = mergeKLists(lists);
    assertLinkedListEquals(new int[]{1,1,1,2,3,3}, result);
}

// Test case 6: Empty input array
// Input: []
// Expected: null
@Test
public void testEmptyArray() {
    ListNode[] lists = new ListNode[0];
    ListNode result = mergeKLists(lists);
    assertNull(result);
}

// Helper method for testing
private void assertLinkedListEquals(int[] expected, ListNode actual) {
    ListNode current = actual;
    int index = 0;
    
    while (current != null && index < expected.length) {
        assertEquals(expected[index], current.val);
        current = current.next;
        index++;
    }
    
    assertNull(current); // Should be at end
    assertEquals(expected.length, index); // Should have processed all elements
}

11. Final Summary

The core idea is to efficiently merge k sorted linked lists by leveraging a min-heap to always select the smallest available element, maintaining O(n log k) time complexity where n is the total number of elements. This solution works because it reduces the problem to repeatedly finding the minimum element among k candidates, which is optimally solved using a priority queue. The heap-based approach is both time and space efficient, avoiding the need to collect all elements first before sorting, making it ideal for large datasets where memory usage matters.

The key insight is that instead of merging lists sequentially (which would require O(n²) operations), we can maintain a priority queue of size k that allows us to extract the minimum element in O(log k) time, leading to an optimal overall complexity of O(n log k). This approach is particularly efficient when k is much smaller than n, making it well-suited for scenarios with many small sorted lists or streaming data where we want to minimize the number of comparisons needed to find the next smallest element.