What is the brute force approach and complexity for Merge k Sorted Lists?

Copy all values into an array, sort it, then build a new list from the sorted values with time complexity O(N log N) and space complexity O(N).

What is the optimal approach and complexity for Merge k Sorted Lists?

Keep one head per list in a min-heap; pop the smallest and push the next node of that list with optimal time complexity O(N log k) and space complexity O(k).

How do you identify the pattern for Merge k Sorted Lists?

Look for key signals in the prompt: "k sorted linked lists" indicates Each list is sorted, so only its head can be the next node taken from that list. k heads means k candidates.; "merge into one sorted list" indicates Each step takes the smallest candidate → a min-heap of list heads.; "return the head of the merged list" indicates Build the answer by relinking nodes behind a dummy node, not by copying values..

Merge k Sorted Lists

Hard·LeetCode #23 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

You get k linked lists. Each list is already sorted from smallest to largest.

Merge them into one sorted linked list that uses all of the nodes. Return the head of the merged list.

You may relink the existing nodes. You do not need to make copies of the values.

Input

lists: an array of k linked-list heads. A list can be empty, and then its head is null.

Output

The head of one sorted linked list that holds every node from every input list.

Example 1

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

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

Three sorted lists with 8 nodes in total. The merged list holds all 8 nodes in order.

Example 2

Input: lists = []

Output: []

There are no lists, so there are no nodes to return.

Example 3

Input: lists = [[]]

Output: []

The only list is empty.

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

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“k sorted linked lists”

→ Each list is sorted, so only its head can be the next node taken from that list. k heads means k candidates.

“merge into one sorted list”

→ Each step takes the smallest candidate → a min-heap of list heads.

“return the head of the merged list”

→ Build the answer by relinking nodes behind a dummy node, not by copying values.

Approach Complexity Ladder

Brute Force — collect values, sort, rebuildO(N log N)O(N)

Copy all values into an array, sort it, then build a new list from the sorted values

Better — merge one list at a timeO(N · k)O(1)

Merge the result with each list in turn, using the two-list merge

Optimal — min-heap of list headsO(N log k)O(k)

Keep one head per list in a min-heap; pop the smallest and push the next node of that list

Brute Force Intuition

Ignore that the lists are already sorted. Walk every list and collect all values into one array, sort the array, and build a new list from the sorted values. With N total nodes, the sort costs O(N log N).

Recognition rule for this sub-pattern:

Push the head of each list; pop the smallest, push its successor.

Remember this · K-way Merge

Trigger

K sorted lists/arrays, kth smallest across sorted rows, smallest range covering all lists.

Think

The next smallest item overall must be the front of some list — which one?

Key question

What do I push back into the heap after popping?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like K-way Merge translate into production architectures and low-level memory mechanics.

LLD Architecture