Merge k Sorted Lists - Practice Coding Problems

Merge k Sorted Lists - Problem

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

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

Input & Output

Example 1 — Three Sorted Lists

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

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

💡 Note: The linked-lists are: [1→4→5], [1→3→4], [2→6]. Merging them results in [1→1→2→3→4→4→5→6]

Example 2 — Empty Lists Array

$ Input: lists = []

› Output: []

💡 Note: No lists to merge, return empty result

Example 3 — Single Empty List

$ Input: lists = [[]]

› Output: []

💡 Note: Only one empty list, result is empty

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

k sorted linked lists with total n nodes

Process

Merge strategy preserving sorted order

Output

Single sorted linked list containing all nodes

Key Takeaway

🎯 Key Insight: Leverage that individual lists are already sorted - use divide and conquer to merge pairwise rather than sorting all values from scratch

Asked in

a Amazon 87 f Facebook 45 G Google 42 M Microsoft 38 🍎 Apple 25

The key insight is to avoid sorting all values from scratch. Instead, leverage the fact that individual lists are already sorted. The divide and conquer approach is optimal: merge lists pairwise until one remains. Time: O(n log k), Space: O(log k).

Common Approaches

Approach	Time	Space	Notes
✓ Min Heap Approach	O(n log k)	O(k)	Use min heap to always extract the smallest value from k list heads
Divide and Conquer	O(n log k)	O(log k)	Merge lists pairwise using divide and conquer strategy
Brute Force - Collect All Values	O(n log n)	O(n)	Extract all values from all lists, sort them, and create new linked list

Min Heap Approach — Algorithm Steps

Step 1: Add all list heads to min heap
Step 2: Extract minimum, add to result
Step 3: Push next node from that list to heap
Step 4: Repeat until heap is empty

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Heap

Add all list heads to min heap

Extract Min

Pop smallest value, add to result

Update Heap

Push next node from same list back to heap

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* solution(struct ListNode** lists, int listsSize) {
    return NULL;
}

int main() {
    printf("[]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log k)

Each of n nodes is pushed/popped from heap of size k, each operation takes O(log k)

⚡ Linearithmic

Space Complexity

O(k)

Heap stores at most k nodes (one from each list)

✓ Linear Space

89.5K Views

Very High Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Min Heap Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler