Abstract / Summary

Merge multiple sorted linked lists into a single sorted linked list.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 60% (5+ million submissions).

Typical patterns to solve this problem:

• Divide And Conquer
• Heap (Priority Queue)
• Linked List
• Merge Sort

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation merges an arbitrary number of sorted singly-linked lists into a single sorted list. It does so by flattening all node values into a dynamic array, sorting that array, and then reconstructing a new linked list from the sorted values. The algorithm is straightforward and leverages the standard library for heavy lifting.

Key Steps

Collecting all node values

All values from the input lists are extracted and stored in a vector<int>. The loop iterates over each list pointer and walks each list until the end, pushing each node’s value onto the vector.

vector<int> all;
for (auto l : lists)
{
    while (l)
    {
        all.push_back(l->val);
        l = l->next;
    }
}

Sorting the collected values

Once every value is gathered, the vector is sorted in ascending order using std::sort. This call internally selects an efficient hybrid sorting algorithm (introsort) that adapts to the data distribution.

sort(all.begin(), all.end());

Rebuilding the merged list

The sorted vector is consumed from the back, creating new ListNode objects that are linked by inserting each new node at the front of the result list. By using the back of the vector, the algorithm avoids the cost of removing from the front of a vector.

ListNode* head = nullptr;
while (!all.empty())
{
    head = new ListNode(all.back(), head);
    all.pop_back();
}

Returning the result

Finally, the head pointer of the newly constructed list is returned to the caller.

return head;

Edge Cases Handled

When the input lists container is empty, the outer for loop executes zero times, leaving the all vector empty. The subsequent sort operates on an empty range, which is a no-op, and the reconstruction loop terminates immediately, resulting in a nullptr return value that correctly represents an empty merged list.

If any individual list pointer inside lists is nullptr, the inner while (l) guard prevents dereferencing a null pointer, so the algorithm simply skips that list without error.

Lists that contain a single node are processed correctly: the node’s value is added to all, sorted (trivially), and a new node with the same value is created in the output list.

Duplicate values across different input lists are preserved because each value is individually pushed onto all. The sort maintains the relative order of equal elements, and the reconstruction step creates a distinct node for each occurrence, ensuring the merged list contains the correct multiplicity.

Performance Optimizations Observed

The use of a contiguous vector<int> for temporary storage provides cache-friendly access patterns during both the collection and sorting phases. std::sort operates in-place on this contiguous memory, benefiting from locality and branch prediction.

Rebuilding the list by prepending nodes (head = new ListNode(value, head)) eliminates the need to traverse to the tail for each insertion. This yields linear time construction of the output list, as each insertion is O(1) and no additional pointer updates are required.

Consuming the vector from the back (all.back() and pop_back()) avoids the linear-time cost associated with removing elements from the front of a vector. This choice keeps the reconstruction loop efficient, maintaining overall linear work for the list creation step.

By allocating new nodes only once per value and never reallocating existing nodes, the algorithm avoids unnecessary memory churn and leverages the allocator’s bulk allocation strategies for the short-lived vector.

Imagine having many different toy boxes scattered all over the floor, and in each box, there are some colorful plastic blocks lined up in a row. The goal is to collect all of those blocks and put them into one long, neat train where the blocks are arranged in order from the smallest number to the biggest number.

First, the code travels to every single box one by one. It looks at the first block in a box, writes down the number written on it, and then moves to the next block until the box is completely empty. It keeps doing this for every box until every single number from every block is gathered into one big pile, just like taking all the toys out and putting them in a single heap on the rug.

Once all the numbers are in the pile, the code organizes them. It sorts the numbers so that the smallest ones are at one end and the largest ones are at the other, much like lining up children by how tall they are.

Finally, the code takes the sorted pile of numbers and starts building a new chain. It reaches for the biggest number first and attaches it to the front of the list, then it grabs the next biggest and puts it in front of that, and so on. It repeats this until it has built a brand new, perfectly sorted train made out of all the blocks from those messy boxes.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python			Java									TS
	WalkCCC	C++	Python			Java
	leetcode.ca	C++	Python	C#	Rust	Java		JS		Ruby		Go		PHP	TS
	LeetcodeHelp	C++	Python			Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python			Java
github	aylei				Rust
	begeekmyfriend						C
	BigEggStudy			C#
	black-shadows	C++
	bujosa				Rust
	charles-wangkai					Java
	chenyanzhe	C++
	everthis							JS
	fartem									Ruby
	FelixFan1122			C#
	fengvyi	C++
	fpdjsns	C++
	gaosq0604		Python
	Garvit244		Python
	gouthampradhan					Java
	halfrost											Go
	haoel	C++
	JoshCrozier							JS
	keineahnung2345	C++
	lennylxx						C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	martianoff								Scala
	qiyuangong		Python
	ruoru				Rust
	Shamik07												Dart
	shreymehul			C#
	sonugiri1043	C++
	suxrobGM			C#
	varunu28					Java
	vli02						C
	XiaotaoGuo	C++
	yuanliu666										Kotlin
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, PHP, Python, Ruby, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Rust
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
martianoff	Scala
qiyuangong	Python
ruoru	Rust
Shamik07	Dart
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
XiaotaoGuo	C++
yuanliu666	Kotlin
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality