Limited Time Offer:Up to 25% off Hello Interview Premium

⌘K

Tutor

Get Premium

Leetcode 23. Merge k Sorted Lists

Asked at:

DESCRIPTION

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Input:

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

Output:

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

Explanation: The three input lists are merged into one sorted list by repeatedly selecting the smallest head node

Constraints:

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] is sorted in ascending order
The sum of lists[i].length will not exceed 10^4

Understanding the Problem

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?

Brute Force Approach

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.

Building Intuition

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.

Common Mistakes

Forgetting to handle empty lists in the input - always check if a list is null or empty before accessing its head

Not advancing the pointer after extracting a node - after taking a node from a list, you must move to its next node (if it exists) and add it to the heap

Comparing node objects instead of node values in the heap - the heap should compare based on node.val, not the node references themselves

Creating a new node for each value instead of reusing existing nodes - you should link the actual nodes from the input lists, not create copies

Off-by-one errors when initializing the heap - make sure to add the first node from each non-empty list, not skip any or add nulls

Optimal Solution

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.

Visualization

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

Start merging k sorted lists

0 / 38

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n log k) We process n total nodes, and each heap operation (insert/extract-min) takes O(log k) time since the heap contains at most k elements

Space Complexity: O(k) The heap stores at most k nodes at any time (one head from each list), requiring O(k) space

What We've Learned

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.

Test Your Understanding

Why is heap the right data structure for this problem?

heap provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Late December, 2025

Oracle

Senior

Early December, 2025

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 23. Merge k Sorted Lists

DESCRIPTION

Understanding the Problem

Brute Force Approach

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact