Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Merge k Sorted Lists

HARDProblemSolveExternal Links

Description

You are given an array containing k linked lists, where each linked list is sorted in ascending order (smallest to largest values).

Your task is to merge all these k linked lists into a single linked list that is also sorted in ascending order, and return the head of this merged list.

Think of it like having multiple stacks of papers, each stack already organized from smallest to largest number on top. You need to combine all stacks into one big stack while keeping everything in order.

Key Points:

  • Each input linked list is already sorted
  • You need to produce one combined sorted linked list
  • The input array of lists could be empty, or could contain empty lists

Examples

Example 1

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

Output: [1,1,2,3,4,4,5,6]

Explanation: We have three linked lists:

  • List 1: 1 → 4 → 5
  • List 2: 1 → 3 → 4
  • List 3: 2 → 6

To merge them, we compare the heads of all lists and pick the smallest value each time:

  • Compare 1, 1, 2 → Pick 1 from List 1
  • Compare 4, 1, 2 → Pick 1 from List 2
  • Compare 4, 3, 2 → Pick 2 from List 3
  • Compare 4, 3, 6 → Pick 3 from List 2
  • Compare 4, 4, 6 → Pick 4 from List 1
  • Compare 5, 4, 6 → Pick 4 from List 2 (List 2 now empty)
  • Compare 5, 6 → Pick 5 from List 1 (List 1 now empty)
  • Only 6 left → Pick 6 from List 3

Final merged list: 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6

Example 2

Input: lists = []

Output: []

Explanation: The input array is empty, meaning there are no linked lists to merge. We return an empty list since there's nothing to combine.

Example 3

Input: lists = [[]]

Output: []

Explanation: The input array contains one linked list, but that linked list is empty (has no nodes). Since there are no actual elements to merge, we return an empty list.

Example 4

Input: lists = [[5], [2], [9], [1]]

Output: [1,2,5,9]

Explanation: Each list contains just one element. We simply need to sort these single elements:

  • List 1: 5
  • List 2: 2
  • List 3: 9
  • List 4: 1

After merging in sorted order: 1 → 2 → 5 → 9

Constraints

  • k == lists.length (k is the number of linked lists)
  • 0 ≤ k ≤ 10^4
  • 0 ≤ lists[i].length ≤ 500 (each list can have up to 500 nodes)
  • -10^4 ≤ lists[i][j] ≤ 10^4 (node values range from -10000 to 10000)
  • Each lists[i] is sorted in ascending order
  • The sum of all lists[i].length will not exceed 10^4 (total nodes across all lists ≤ 10000)

Editorial

Brute Force - Compare All Heads

Intuition

The most straightforward approach mimics how a human would solve this problem manually. If you had k stacks of sorted papers in front of you, you would look at the top paper of each stack, find the smallest number, take that paper and put it in your result pile, then repeat.

For our linked lists, we do exactly this:

  1. Look at the head (first node) of all k lists
  2. Find which head has the smallest value
  3. Remove that node and add it to our result list
  4. Repeat until all lists are empty

This approach is intuitive because it directly applies the logic we would use in real life. Each time we pick the globally smallest available element, which guarantees our result stays sorted.

Step-by-Step Explanation

Let's trace through with lists = [[1,4,5], [1,3,4], [2,6]]

Initial state:
List 0: 1 → 4 → 5
List 1: 1 → 3 → 4  
List 2: 2 → 6
Result: empty

Step 1: Compare heads of all lists: 1, 1, 2

  • Minimum value is 1 (at List 0)
  • Add 1 to result, advance List 0's head
List 0: 4 → 5
List 1: 1 → 3 → 4
List 2: 2 → 6
Result: 1

Step 2: Compare heads: 4, 1, 2

  • Minimum is 1 (at List 1)
  • Add 1 to result, advance List 1's head
List 0: 4 → 5
List 1: 3 → 4
List 2: 2 → 6
Result: 1 → 1

Step 3: Compare heads: 4, 3, 2

  • Minimum is 2 (at List 2)
  • Add 2 to result, advance List 2's head
List 0: 4 → 5
List 1: 3 → 4
List 2: 6
Result: 1 → 1 → 2

Step 4: Compare heads: 4, 3, 6

  • Minimum is 3 (at List 1)
  • Add 3 to result, advance List 1's head
List 0: 4 → 5
List 1: 4
List 2: 6
Result: 1 → 1 → 2 → 3

Step 5: Compare heads: 4, 4, 6

  • Minimum is 4 (at List 0, we can pick either 4)
  • Add 4 to result, advance List 0's head
List 0: 5
List 1: 4
List 2: 6
Result: 1 → 1 → 2 → 3 → 4

Step 6: Compare heads: 5, 4, 6

  • Minimum is 4 (at List 1)
  • Add 4 to result, advance List 1's head (List 1 now empty)
List 0: 5
List 1: empty
List 2: 6
Result: 1 → 1 → 2 → 3 → 4 → 4

Step 7: Compare heads: 5, 6 (skip empty list)

  • Minimum is 5 (at List 0)
  • Add 5 to result, advance List 0's head (List 0 now empty)
List 0: empty
List 1: empty  
List 2: 6
Result: 1 → 1 → 2 → 3 → 4 → 4 → 5

Step 8: Only List 2 remains with 6

  • Add 6 to result (List 2 now empty)
All lists: empty
Result: 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6

Final Answer: 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6

Algorithm

  1. Create a dummy node to serve as the head of our result list
  2. Create a current pointer starting at the dummy node
  3. While at least one list is non-empty:
    a. Scan through all k list heads to find the minimum value
    b. Track which list contains this minimum
    c. Attach this minimum node to current.next
    d. Move current forward
    e. Advance the head of the list where we took the minimum
  4. Return dummy.next (the actual head of merged list)

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // Handle edge case: no lists provided
        if (lists.empty()) {
            return nullptr;
        }
        
        // Create dummy node to simplify list building
        ListNode* dummy = new ListNode(-1);
        ListNode* current = dummy;
        
        // Continue until all lists are exhausted
        while (true) {
            int minIndex = -1;
            ListNode* minNode = nullptr;
            
            // Find the list with the smallest head value
            for (int i = 0; i < lists.size(); i++) {
                if (lists[i] != nullptr) {
                    if (minNode == nullptr || lists[i]->val < minNode->val) {
                        minNode = lists[i];
                        minIndex = i;
                    }
                }
            }
            
            // If no valid node found, all lists are empty
            if (minIndex == -1) {
                break;
            }
            
            // Add the minimum node to result
            current->next = minNode;
            current = current->next;
            
            // Advance the head of the list we took from
            lists[minIndex] = lists[minIndex]->next;
        }
        
        return dummy->next;
    }
};
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeKLists(self, lists: list[ListNode]) -> ListNode:
        # Handle edge case: no lists provided
        if not lists:
            return None
        
        # Create dummy node to simplify list building
        dummy = ListNode(-1)
        current = dummy
        
        # Continue until all lists are exhausted
        while True:
            min_index = -1
            min_node = None
            
            # Find the list with the smallest head value
            for i in range(len(lists)):
                if lists[i] is not None:
                    if min_node is None or lists[i].val < min_node.val:
                        min_node = lists[i]
                        min_index = i
            
            # If no valid node found, all lists are empty
            if min_index == -1:
                break
            
            # Add the minimum node to result
            current.next = min_node
            current = current.next
            
            # Advance the head of the list we took from
            lists[min_index] = lists[min_index].next
        
        return dummy.next
/**
 * 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 case: no lists provided
        if (lists == null || lists.length == 0) {
            return null;
        }
        
        // Create dummy node to simplify list building
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;
        
        // Continue until all lists are exhausted
        while (true) {
            int minIndex = -1;
            ListNode minNode = null;
            
            // Find the list with the smallest head value
            for (int i = 0; i < lists.length; i++) {
                if (lists[i] != null) {
                    if (minNode == null || lists[i].val < minNode.val) {
                        minNode = lists[i];
                        minIndex = i;
                    }
                }
            }
            
            // If no valid node found, all lists are empty
            if (minIndex == -1) {
                break;
            }
            
            // Add the minimum node to result
            current.next = minNode;
            current = current.next;
            
            // Advance the head of the list we took from
            lists[minIndex] = lists[minIndex].next;
        }
        
        return dummy.next;
    }
}

Complexity Analysis

Time Complexity: O(N × k)

Where N is the total number of nodes across all lists, and k is the number of lists.

  • We process each of the N nodes exactly once
  • For each node we process, we scan through k list heads to find the minimum
  • This gives us N × k operations total

In the worst case with the given constraints (N up to 10^4 and k up to 10^4), this could be up to 10^8 operations.

Space Complexity: O(1)

We only use a constant amount of extra space:

  • A dummy node pointer
  • A current pointer
  • Variables to track minimum index and node

We reuse the existing nodes from the input lists rather than creating new nodes.

Why This Approach Is Not Efficient

The brute force approach has a significant inefficiency: we scan through all k list heads every time we want to find the minimum value.

Let's analyze with the problem constraints:

  • Total nodes N can be up to 10^4
  • Number of lists k can be up to 10^4
  • Worst case: 10^4 × 10^4 = 10^8 operations

This is borderline for typical time limits of 1-2 seconds. More importantly, scanning k elements to find a minimum is wasteful because we're doing redundant comparisons. After picking a minimum, most of the k-1 other values remain unchanged, yet we compare them all again.

The key insight is: finding the minimum among k elements can be done in O(log k) time using a min-heap data structure, instead of O(k) time with linear scanning.

We need a data structure that:

  1. Quickly gives us the minimum element
  2. Efficiently handles removing the minimum and adding new elements

A min-heap (priority queue) provides exactly these properties.

Better Approach - Merge Lists One by One

Intuition

Before jumping to the heap solution, let's consider another intuitive approach that builds on a simpler problem: merging two sorted lists.

Merging two sorted lists is straightforward - we use two pointers and compare elements one by one. This is an O(n) operation where n is the total length of both lists.

For k lists, we can apply this repeatedly:

  1. Start with the first list as our "result"
  2. Merge the second list into our result
  3. Merge the third list into our result
  4. Continue until all lists are merged

This approach reuses our knowledge of the simpler two-list merge problem and extends it to handle k lists.

Step-by-Step Explanation

Let's trace through with lists = [[1,4,5], [1,3,4], [2,6]]

Step 1: Initialize result with the first list

Result: 1 → 4 → 5
Remaining: [1,3,4], [2,6]

Step 2: Merge result with second list [1,3,4]

  • Compare 1 and 1: both equal, take from result → merged: 1
  • Compare 4 and 1: take 1 from second list → merged: 1 → 1
  • Compare 4 and 3: take 3 from second list → merged: 1 → 1 → 3
  • Compare 4 and 4: both equal, take from result → merged: 1 → 1 → 3 → 4
  • Compare 5 and 4: take 4 from second list → merged: 1 → 1 → 3 → 4 → 4
  • Second list exhausted, append remaining: 5
Result: 1 → 1 → 3 → 4 → 4 → 5
Remaining: [2,6]

Step 3: Merge result with third list [2,6]

  • Compare 1 and 2: take 1 → merged: 1
  • Compare 1 and 2: take 1 → merged: 1 → 1
  • Compare 3 and 2: take 2 → merged: 1 → 1 → 2
  • Compare 3 and 6: take 3 → merged: 1 → 1 → 2 → 3
  • Compare 4 and 6: take 4 → merged: 1 → 1 → 2 → 3 → 4
  • Compare 4 and 6: take 4 → merged: 1 → 1 → 2 → 3 → 4 → 4
  • Compare 5 and 6: take 5 → merged: 1 → 1 → 2 → 3 → 4 → 4 → 5
  • Result exhausted, append remaining: 6
Result: 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6

Final Answer: 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6

Algorithm

  1. Handle edge case: if lists array is empty, return null
  2. Initialize result as the first list (lists[0])
  3. For each remaining list i from 1 to k-1:
    a. Merge result with lists[i] using two-pointer technique
    b. Update result to the newly merged list
  4. Return result

Helper function - Merge Two Lists:

  1. Create a dummy node
  2. Use two pointers, one for each list
  3. Compare values and attach the smaller one to result
  4. Advance the pointer of the list we took from
  5. When one list is exhausted, attach the remainder of the other
  6. Return dummy.next

Code

class Solution {
private:
    // Helper function to merge two sorted lists
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummy = new ListNode(-1);
        ListNode* current = dummy;
        
        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val <= list2->val) {
                current->next = list1;
                list1 = list1->next;
            } else {
                current->next = list2;
                list2 = list2->next;
            }
            current = current->next;
        }
        
        // Attach remaining nodes
        if (list1 != nullptr) {
            current->next = list1;
        } else {
            current->next = list2;
        }
        
        return dummy->next;
    }
    
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) {
            return nullptr;
        }
        
        // Start with the first list
        ListNode* result = lists[0];
        
        // Merge each subsequent list into result
        for (int i = 1; i < lists.size(); i++) {
            result = mergeTwoLists(result, lists[i]);
        }
        
        return result;
    }
};
class Solution:
    def mergeKLists(self, lists: list[ListNode]) -> ListNode:
        if not lists:
            return None
        
        def merge_two_lists(list1: ListNode, list2: ListNode) -> ListNode:
            """Helper function to merge two sorted lists"""
            dummy = ListNode(-1)
            current = dummy
            
            while list1 is not None and list2 is not None:
                if list1.val <= list2.val:
                    current.next = list1
                    list1 = list1.next
                else:
                    current.next = list2
                    list2 = list2.next
                current = current.next
            
            # Attach remaining nodes
            current.next = list1 if list1 is not None else list2
            
            return dummy.next
        
        # Start with the first list
        result = lists[0]
        
        # Merge each subsequent list into result
        for i in range(1, len(lists)):
            result = merge_two_lists(result, lists[i])
        
        return result
class Solution {
    // Helper function to merge two sorted lists
    private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;
        
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }
        
        // Attach remaining nodes
        if (list1 != null) {
            current.next = list1;
        } else {
            current.next = list2;
        }
        
        return dummy.next;
    }
    
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        
        // Start with the first list
        ListNode result = lists[0];
        
        // Merge each subsequent list into result
        for (int i = 1; i < lists.length; i++) {
            result = mergeTwoLists(result, lists[i]);
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(N × k)

Where N is the total number of nodes and k is the number of lists.

Let's assume each list has approximately n = N/k nodes for simplicity:

  • First merge: n + n = 2n comparisons
  • Second merge: 2n + n = 3n comparisons
  • Third merge: 3n + n = 4n comparisons
  • ...
  • (k-1)th merge: (k-1)n + n = kn comparisons

Total: 2n + 3n + 4n + ... + kn = n × (2 + 3 + 4 + ... + k) = n × (k(k+1)/2 - 1) ≈ O(n × k²) = O(N × k)

This simplifies to O(N × k) where N is total nodes.

Space Complexity: O(1)

We only use constant extra space for pointers. The merged list reuses existing nodes.

Why This Approach Is Not Efficient

While the merge-one-by-one approach is intuitive, it has a hidden inefficiency: the same nodes get visited multiple times.

Consider what happens:

  • After merging lists 1 and 2, we have a result of length 2n
  • When merging with list 3, we traverse all 2n nodes of our result again
  • When merging with list 4, we traverse all 3n nodes again
  • And so on...

Nodes from early lists get traversed over and over. The first list's nodes are visited k-1 times, the second list's nodes are visited k-2 times, etc.

With k = 10^4 lists, this leads to approximately O(N × k) = O(10^8) operations, which is too slow.

The key insight is: instead of merging linearly (one after another), we can merge in pairs, halving the number of lists each round. This is the Divide and Conquer approach.

Alternatively, we can use a Min-Heap to always efficiently track the smallest available element across all lists.

Optimal Approach 1 - Min Heap (Priority Queue)

Intuition

The key bottleneck in our brute force was finding the minimum among k list heads - this took O(k) time for each of the N nodes.

A Min-Heap is a data structure that:

  1. Always keeps the minimum element at the top
  2. Supports insertion in O(log k) time
  3. Supports extracting minimum in O(log k) time

Our strategy:

  1. Insert all k list heads into a min-heap
  2. Extract the minimum node (this is our next result node)
  3. If that node has a next node, insert it into the heap
  4. Repeat until the heap is empty

The heap always contains at most k elements (one per list), so all operations are O(log k) instead of O(k).

Think of the heap like a smart assistant who always knows which stack of papers has the smallest number on top, without you having to scan through all stacks manually each time.

Step-by-Step Explanation

Let's trace through with lists = [[1,4,5], [1,3,4], [2,6]]

Initialization: Add all heads to min-heap

Heap: [(1, list0), (1, list1), (2, list2)]  (min-heap by value)
Result: empty

Step 1: Extract min = 1 from list0

  • Add 1 to result
  • Insert next node (4) from list0 into heap
Heap: [(1, list1), (2, list2), (4, list0)]
Result: 1

Step 2: Extract min = 1 from list1

  • Add 1 to result
  • Insert next node (3) from list1 into heap
Heap: [(2, list2), (3, list1), (4, list0)]
Result: 1 → 1

Step 3: Extract min = 2 from list2

  • Add 2 to result
  • Insert next node (6) from list2 into heap
Heap: [(3, list1), (4, list0), (6, list2)]
Result: 1 → 1 → 2

Step 4: Extract min = 3 from list1

  • Add 3 to result
  • Insert next node (4) from list1 into heap
Heap: [(4, list0), (4, list1), (6, list2)]
Result: 1 → 1 → 2 → 3

Step 5: Extract min = 4 from list0

  • Add 4 to result
  • Insert next node (5) from list0 into heap
Heap: [(4, list1), (5, list0), (6, list2)]
Result: 1 → 1 → 2 → 3 → 4

Step 6: Extract min = 4 from list1

  • Add 4 to result
  • list1 is now empty, nothing to insert
Heap: [(5, list0), (6, list2)]
Result: 1 → 1 → 2 → 3 → 4 → 4

Step 7: Extract min = 5 from list0

  • Add 5 to result
  • list0 is now empty, nothing to insert
Heap: [(6, list2)]
Result: 1 → 1 → 2 → 3 → 4 → 4 → 5

Step 8: Extract min = 6 from list2

  • Add 6 to result
  • list2 is now empty, nothing to insert
Heap: []
Result: 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6

Heap is empty - we're done!

Final Answer: 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6

Merge K Sorted Lists — Min-Heap Extraction — A min-heap holds the current head of each list. We repeatedly extract the minimum, append it to the result, and push that node's successor back into the heap. The heap always has at most k entries, so each operation is O(log k).

Algorithm

  1. Handle edge case: if lists array is empty, return null
  2. Create a min-heap (priority queue) that orders nodes by their value
  3. Insert the head of each non-empty list into the heap
  4. Create a dummy node for result list building
  5. While the heap is not empty:
    a. Extract the node with minimum value from heap
    b. Append this node to our result list
    c. If this node has a next node, insert it into the heap
  6. Return dummy.next

Code

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // Custom comparator for min-heap: smaller values have higher priority
        auto compare = [](ListNode* a, ListNode* b) {
            return a->val > b->val;  // Note: > for min-heap in C++
        };
        
        // Min-heap of ListNode pointers
        priority_queue<ListNode*, vector<ListNode*>, decltype(compare)> minHeap(compare);
        
        // Add all non-null heads to the heap
        for (ListNode* list : lists) {
            if (list != nullptr) {
                minHeap.push(list);
            }
        }
        
        // Dummy node for result list
        ListNode* dummy = new ListNode(-1);
        ListNode* current = dummy;
        
        // Process nodes until heap is empty
        while (!minHeap.empty()) {
            // Get the node with smallest value
            ListNode* smallest = minHeap.top();
            minHeap.pop();
            
            // Add to result list
            current->next = smallest;
            current = current->next;
            
            // If this node has a next, add it to heap
            if (smallest->next != nullptr) {
                minHeap.push(smallest->next);
            }
        }
        
        return dummy->next;
    }
};
import heapq

class Solution:
    def mergeKLists(self, lists: list[ListNode]) -> ListNode:
        # Min-heap: (node_value, unique_counter, node)
        # unique_counter is needed because ListNode objects are not comparable
        min_heap = []
        counter = 0  # Tie-breaker for nodes with equal values
        
        # Add all non-null heads to the heap
        for list_head in lists:
            if list_head is not None:
                heapq.heappush(min_heap, (list_head.val, counter, list_head))
                counter += 1
        
        # Dummy node for result list
        dummy = ListNode(-1)
        current = dummy
        
        # Process nodes until heap is empty
        while min_heap:
            # Get the node with smallest value
            value, _, smallest = heapq.heappop(min_heap)
            
            # Add to result list
            current.next = smallest
            current = current.next
            
            # If this node has a next, add it to heap
            if smallest.next is not None:
                heapq.heappush(min_heap, (smallest.next.val, counter, smallest.next))
                counter += 1
        
        return dummy.next
import java.util.PriorityQueue;

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        
        // Min-heap with custom comparator: order by node value
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
            (a, b) -> a.val - b.val
        );
        
        // Add all non-null heads to the heap
        for (ListNode list : lists) {
            if (list != null) {
                minHeap.offer(list);
            }
        }
        
        // Dummy node for result list
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;
        
        // Process nodes until heap is empty
        while (!minHeap.isEmpty()) {
            // Get the node with smallest value
            ListNode smallest = minHeap.poll();
            
            // Add to result list
            current.next = smallest;
            current = current.next;
            
            // If this node has a next, add it to heap
            if (smallest.next != null) {
                minHeap.offer(smallest.next);
            }
        }
        
        return dummy.next;
    }
}

Complexity Analysis

Time Complexity: O(N × log k)

Where N is the total number of nodes across all lists, and k is the number of lists.

  • The heap contains at most k elements at any time (one from each list)
  • Each of the N nodes is inserted into the heap exactly once: O(log k) per insertion
  • Each of the N nodes is extracted from the heap exactly once: O(log k) per extraction
  • Total: N insertions + N extractions = O(N × log k)

With N = 10^4 and k = 10^4, this is approximately 10^4 × 14 ≈ 1.4 × 10^5 operations, which is very efficient.

Space Complexity: O(k)

The heap stores at most k nodes at any given time (the current head of each non-empty list). This is a significant improvement when k is large.

Optimal Approach 2 - Divide and Conquer

Intuition

Another optimal approach uses the Divide and Conquer paradigm, similar to Merge Sort.

Instead of merging lists one by one (which causes repeated traversals), we:

  1. Divide: Split the k lists into two halves
  2. Conquer: Recursively merge each half
  3. Combine: Merge the two resulting sorted lists

This is like a tournament bracket:

  • Round 1: Merge pairs of adjacent lists (k/2 merges)
  • Round 2: Merge pairs of results (k/4 merges)
  • Continue until one list remains

The key advantage: each node is visited only O(log k) times instead of O(k) times, because there are only log k levels of merging.

Visualize it like this:

Level 3: [merged list of all 8]
              ↑
Level 2: [merged 1-4]  [merged 5-8]
              ↑              ↑
Level 1: [1-2] [3-4]    [5-6] [7-8]
              ↑    ↑      ↑     ↑
Level 0:  1  2  3  4    5  6  7  8

Step-by-Step Explanation

Let's trace through with lists = [[1,4,5], [1,3,4], [2,6]]

We have 3 lists, so we'll divide and conquer:

Top-level call: mergeKLists([list0, list1, list2])

  • Divide: left half = [list0], right half = [list1, list2]

Left recursive call: mergeKLists([list0])

  • Only one list, return it directly
  • Returns: 1 → 4 → 5

Right recursive call: mergeKLists([list1, list2])

  • Divide: left = [list1], right = [list2]

    Left sub-call: mergeKLists([list1])

    • Only one list, return it directly
    • Returns: 1 → 3 → 4

    Right sub-call: mergeKLists([list2])

    • Only one list, return it directly
    • Returns: 2 → 6

  • Merge: (1 → 3 → 4) and (2 → 6)

    • Compare 1, 2 → take 1
    • Compare 3, 2 → take 2
    • Compare 3, 6 → take 3
    • Compare 4, 6 → take 4
    • Remaining: 6

  • Returns: 1 → 2 → 3 → 4 → 6

Back to top-level: Merge left result and right result

  • Left: 1 → 4 → 5

  • Right: 1 → 2 → 3 → 4 → 6

  • Compare 1, 1 → take 1 (from left)

  • Compare 4, 1 → take 1 (from right)

  • Compare 4, 2 → take 2

  • Compare 4, 3 → take 3

  • Compare 4, 4 → take 4 (from left)

  • Compare 5, 4 → take 4 (from right)

  • Compare 5, 6 → take 5

  • Remaining: 6

Final Answer: 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6

Algorithm

  1. Base cases:
    • If lists array is empty, return null
    • If lists has only one list, return that list
  2. Find the middle index: mid = length / 2
  3. Recursively merge the left half: left = mergeKLists(lists[0...mid-1])
  4. Recursively merge the right half: right = mergeKLists(lists[mid...end])
  5. Merge the two resulting lists using two-pointer technique
  6. Return the merged result

Helper function - Merge Two Lists: (same as before)

  1. Create a dummy node
  2. Compare heads, attach smaller one, advance that pointer
  3. Repeat until one list is exhausted
  4. Attach remaining nodes
  5. Return dummy.next

Code

class Solution {
private:
    // Helper function to merge two sorted lists
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummy = new ListNode(-1);
        ListNode* current = dummy;
        
        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val <= list2->val) {
                current->next = list1;
                list1 = list1->next;
            } else {
                current->next = list2;
                list2 = list2->next;
            }
            current = current->next;
        }
        
        current->next = (list1 != nullptr) ? list1 : list2;
        return dummy->next;
    }
    
    // Divide and conquer: merge lists from index start to end
    ListNode* mergeRange(vector<ListNode*>& lists, int start, int end) {
        // Base case: empty range
        if (start > end) {
            return nullptr;
        }
        
        // Base case: single list
        if (start == end) {
            return lists[start];
        }
        
        // Divide: split into two halves
        int mid = start + (end - start) / 2;
        
        // Conquer: recursively merge each half
        ListNode* left = mergeRange(lists, start, mid);
        ListNode* right = mergeRange(lists, mid + 1, end);
        
        // Combine: merge the two halves
        return mergeTwoLists(left, right);
    }
    
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) {
            return nullptr;
        }
        return mergeRange(lists, 0, lists.size() - 1);
    }
};
class Solution:
    def mergeKLists(self, lists: list[ListNode]) -> ListNode:
        
        def merge_two_lists(list1: ListNode, list2: ListNode) -> ListNode:
            """Helper function to merge two sorted lists"""
            dummy = ListNode(-1)
            current = dummy
            
            while list1 is not None and list2 is not None:
                if list1.val <= list2.val:
                    current.next = list1
                    list1 = list1.next
                else:
                    current.next = list2
                    list2 = list2.next
                current = current.next
            
            current.next = list1 if list1 is not None else list2
            return dummy.next
        
        def merge_range(start: int, end: int) -> ListNode:
            """Divide and conquer: merge lists from index start to end"""
            # Base case: empty range
            if start > end:
                return None
            
            # Base case: single list
            if start == end:
                return lists[start]
            
            # Divide: split into two halves
            mid = start + (end - start) // 2
            
            # Conquer: recursively merge each half
            left = merge_range(start, mid)
            right = merge_range(mid + 1, end)
            
            # Combine: merge the two halves
            return merge_two_lists(left, right)
        
        if not lists:
            return None
        
        return merge_range(0, len(lists) - 1)
class Solution {
    // Helper function to merge two sorted lists
    private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;
        
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }
        
        current.next = (list1 != null) ? list1 : list2;
        return dummy.next;
    }
    
    // Divide and conquer: merge lists from index start to end
    private ListNode mergeRange(ListNode[] lists, int start, int end) {
        // Base case: empty range
        if (start > end) {
            return null;
        }
        
        // Base case: single list
        if (start == end) {
            return lists[start];
        }
        
        // Divide: split into two halves
        int mid = start + (end - start) / 2;
        
        // Conquer: recursively merge each half
        ListNode left = mergeRange(lists, start, mid);
        ListNode right = mergeRange(lists, mid + 1, end);
        
        // Combine: merge the two halves
        return mergeTwoLists(left, right);
    }
    
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        return mergeRange(lists, 0, lists.length - 1);
    }
}

Complexity Analysis

Time Complexity: O(N × log k)

Where N is the total number of nodes across all lists, and k is the number of lists.

  • There are log k levels in our divide and conquer tree
  • At each level, we process all N nodes exactly once (through merging)
  • Total work: N nodes × log k levels = O(N × log k)

Another way to see it:

  • Level 0: k lists, each with N/k nodes
  • Level 1: k/2 merges, each processing 2×(N/k) nodes → total N nodes
  • Level 2: k/4 merges, each processing 4×(N/k) nodes → total N nodes
  • ...
  • Each of log k levels processes N nodes → O(N × log k)

Space Complexity: O(log k)

The recursion depth is log k (since we halve the number of lists at each level). Each recursive call uses constant extra space, so the total space for the call stack is O(log k).

Note: If we count the output list, that would be O(N), but we typically don't count output space in complexity analysis.

Comparison of Approaches

ApproachTime ComplexitySpace ComplexityWhen to Use
Brute Force (Compare All Heads)O(N × k)O(1)Only for small k
Merge One by OneO(N × k)O(1)Simple to implement, small k
Min HeapO(N × log k)O(k)General case, especially when lists have varying sizes
Divide and ConquerO(N × log k)O(log k)General case, especially when lists have similar sizes

Summary:

  • For small k (< 10), any approach works fine
  • For large k, use Min Heap or Divide and Conquer
  • Min Heap is slightly more intuitive and handles varying list sizes better
  • Divide and Conquer uses less space (O(log k) vs O(k)) if space is a concern
  • Both optimal approaches achieve O(N × log k) time, which is the best possible for this problem