Log inSign up
hardLeetCodeNot Started

Merge k Sorted Lists

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Heap
Solve on LeetCode
Lesson

Problem Statement

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 single sorted linked list and return its head.

Example 1 · Example 1: Three Linked Lists:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are: 1->4->5 1->3->4 2->6 Merging them into one sorted list: 1->1->2->3->4->4->5->6. Min-Heap (Initial Heads): (1, L0) / \ (1, L1) (2, L2)

Example 2 · Example 2: Empty Lists:

Input: lists = []
Output: []
Explanation: No lists to merge; returns null/empty.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Implement K-way merge on linked list data structures.
  • Custom comparator on ListNode objects in C++, Java, Python, and JavaScript.
  • Master Divide and Conquer pairwise merging.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Merge K sorted collections into one sorted collection.
  • Linked list node pointer manipulations.
  • Classic K-way merge pattern.

Algorithmic Decision Tree:

  • Iterative 1-by-1 merge takes O(N * K) which times out.
  • Min-Heap of size K takes O(N log K) time and O(K) space.
  • Divide and conquer merges pairs in O(N log K) time and O(1) auxiliary space.

Connected Patterns:

Find K Pairs with Smallest SumsKth Smallest Element in a Sorted MatrixMerge Two Sorted Lists

1. Brute Force — Collect Node Values and Rebuild

Intuition

Traverse each list and store all node values in a dynamic array. Sort the array. Then create new linked list nodes for each value in sorted order.

When to apply: When pointer manipulation is tricky and extra memory is unconstrained.

Algorithm

  1. Step 1: Traverse all lists and push values into vector.
  2. Step 2: Sort vector ascending.
  3. Step 3: Build a new linked list from sorted values.
  4. Step 4: Return head of new linked list.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6struct ListNode {
7 int val;
8 ListNode *next;
9 ListNode(int x) : val(x), next(nullptr) {}
10};
11
12class Solution {
13public:
14 ListNode* mergeKLists(vector<ListNode*>& lists) {
15 vector<int> vals;
16 for (auto list : lists) {
17 while (list) {
18 vals.push_back(list->val);
19 list = list->next;
20 }
21 }
22 sort(vals.begin(), vals.end());
23
24 ListNode dummy(0);
25 ListNode* curr = &dummy;
26 for (int v : vals) {
27 curr->next = new ListNode(v);
28 curr = curr->next;
29 }
30 return dummy.next;
31 }
32};
33
34int main() {
35 Solution sol;
36 ListNode* l1 = new ListNode(1); l1->next = new ListNode(4);
37 ListNode* l2 = new ListNode(2); l2->next = new ListNode(3);
38 vector<ListNode*> lists = {l1, l2};
39
40 ListNode* res = sol.mergeKLists(lists);
41 cout << "Merged List (Brute Force): ";
42 while (res) {
43 cout << res->val << " ";
44 res = res->next;
45 }
46 cout << endl;
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(N log N) — O(N log N) from sorting.
  • Space complexity: O(N) — O(N) memory to store values and new nodes.

Why Brute Force Doesn't Scale:

With K = 10,000 and total nodes N = 10,000, sequential merge takes ~108 operations. Min-Heap takes 10,000 * log(10,000) = ~1.3 * 105 operations (1000x faster).

Min-Heap merges 10,000 lists in ~12ms.

2. Better — Divide and Conquer (Pairwise Merge)

Intuition

Pair up the K lists: merge list 0 with 1, 2 with 3, and so on. In each pass, the number of lists is halved (K -> K/2 -> K/4 ... -> 1). Each level processes all N nodes in O(N). Total time is O(N log K).

When to apply: When strict O(1) auxiliary space is required and in-place pointer relinking is preferred.

Algorithm

  1. Step 1: If lists is empty, return null.
  2. Step 2: While lists.length > 1:
  3. Step 3: Pair up lists[i] and lists[i + 1] and merge using mergeTwoLists.
  4. Step 4: Replace lists with the merged pairs.
  5. Step 5: Return lists[0].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5struct ListNode {
6 int val;
7 ListNode *next;
8 ListNode(int x) : val(x), next(nullptr) {}
9};
10
11class Solution {
12 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
13 ListNode dummy(0);
14 ListNode* tail = &dummy;
15 while (l1 && l2) {
16 if (l1->val <= l2->val) {
17 tail->next = l1;
18 l1 = l1->next;
19 } else {
20 tail->next = l2;
21 l2 = l2->next;
22 }
23 tail = tail->next;
24 }
25 tail->next = l1 ? l1 : l2;
26 return dummy.next;
27 }
28
29public:
30 ListNode* mergeKLists(vector<ListNode*>& lists) {
31 if (lists.empty()) return nullptr;
32 int interval = 1;
33 int n = lists.size();
34 while (interval < n) {
35 for (int i = 0; i + interval < n; i += interval * 2) {
36 lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
37 }
38 interval *= 2;
39 }
40 return lists[0];
41 }
42};
43
44int main() {
45 Solution sol;
46 ListNode* l1 = new ListNode(1); l1->next = new ListNode(4);
47 ListNode* l2 = new ListNode(2); l2->next = new ListNode(3);
48 vector<ListNode*> lists = {l1, l2};
49
50 ListNode* res = sol.mergeKLists(lists);
51 cout << "Merged List (Divide & Conquer): ";
52 while (res) {
53 cout << res->val << " ";
54 res = res->next;
55 }
56 cout << endl;
57 return 0;
58}

Time & Space Complexity

  • Time complexity: O(N log K) — O(N log K) across log K levels.
  • Space complexity: O(1) auxiliary — O(1) strict extra memory.

3. Optimal — Min-Heap (Priority Queue)

Intuition

Initialize a Min-Heap with the head node of each non-empty list. The heap holds at most K elements. Repeatedly pop the smallest node, attach it to the tail of our merged list, and if that node has a next node, push node.next into the heap.

When to apply: Standard industry pattern for multi-way merge.

Algorithm

  1. Step 1: Create a Min-Heap with node comparator (a.val vs b.val).
  2. Step 2: Push head node of every non-empty list into heap.
  3. Step 3: Create dummy head; tail = dummy.
  4. Step 4: While heap is not empty:
  5. Step 5: curr = heap.pop().
  6. Step 6: tail.next = curr; tail = tail.next.
  7. Step 7: If curr.next != null, push curr.next to heap.
  8. Step 8: Return dummy.next.

Interactive Trace for Merge k Sorted Lists

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Heap contains the 3 list heads: (1, L0), (1, L1), (2, L2)
Visual state
Values and pointers at this exact step
tree
Root: 1 (L0)
1
Child: 1 (L1)
1
Child: 2 (L2)
2

Node order shown; add connections to display explicit tree edges.

pop: h1
Check / comparison
Top is node 1 (L0).
Decision / next transition
Pop 1, link to result dummy. Push next node 4.
Why this step matters

Step 1: Heap contains the 3 list heads: (1, L0), (1, L1), (2, L2).

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4using namespace std;
5
6struct ListNode {
7 int val;
8 ListNode *next;
9 ListNode(int x) : val(x), next(nullptr) {}
10};
11
12class Solution {
13public:
14 ListNode* mergeKLists(vector<ListNode*>& lists) {
15 auto comp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
16 priority_queue<ListNode*, vector<ListNode*>, decltype(comp)> minHeap(comp);
17
18 for (auto list : lists) {
19 if (list) minHeap.push(list);
20 }
21
22 ListNode dummy(0);
23 ListNode* tail = &dummy;
24
25 while (!minHeap.empty()) {
26 ListNode* curr = minHeap.top();
27 minHeap.pop();
28
29 tail->next = curr;
30 tail = tail->next;
31
32 if (curr->next) {
33 minHeap.push(curr->next);
34 }
35 }
36 return dummy.next;
37 }
38};
39
40int main() {
41 Solution sol;
42 ListNode* l1 = new ListNode(1); l1->next = new ListNode(4);
43 ListNode* l2 = new ListNode(2); l2->next = new ListNode(3);
44 vector<ListNode*> lists = {l1, l2};
45
46 ListNode* res = sol.mergeKLists(lists);
47 cout << "Merged List (Optimal Min-Heap): ";
48 while (res) {
49 cout << res->val << " ";
50 res = res->next;
51 }
52 cout << endl;
53 return 0;
54}

Time & Space Complexity

  • Time complexity: O(N log K) — O(N log K) where N is total node count and K is number of lists.
  • Space complexity: O(K) — O(K) auxiliary space for heap holding at most K heads.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Collect All Values & SortO(N log N)O(N)Traverse all K lists, copy node values into an array, sort the array, construct a new linked list.Full sorting.
2.Better — Divide and Conquer (Pairwise Merge)O(N log K)O(1) auxiliaryPair up lists and merge each pair using standard 2-list merge. Halves number of lists each round.log K merge rounds.
3.Optimal — Min-Heap (Priority Queue)OptimalO(N log K)O(K)Maintain Min-Heap of size K with active list heads. Pop min node, link to output, push node.next.None. Optimal.

Common Pitfalls & Crucial Edge Cases

Pushing null nodes to heap

Must verify if (node != null) before pushing.

Python tie-breaking error

Pushing (node.val, node) causes Python TypeError when node.val is identical because ListNode doesn't implement <. Must use (node.val, i, node) with unique integer i.

Sequential merging 1 by 1

Merging lists sequentially takes O(K * N) time, which times out.

Crucial Edge Cases to Validate:

  • lists is empty ([]) — Returns null.
  • lists contains only null ([null, null]) — Returns null; heap remains empty.
  • Single list in lists ([L0]) — Heap processes L0 and returns it directly.
  • Lists of very unequal lengths — Min-Heap handles different list lengths automatically.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the Python tie-breaker detail '(val, i, node)' — this is an instant differentiator in technical interviews.
  2. Compare Divide & Conquer (O(1) space) and Min-Heap (O(K) space).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must Python tuple in heapq contain the index i (e.g. (node.val, i, node))?

Back to DSA Sheet