Abstract / Summary

Combine two already ordered sequences into one ordered sequence by merging their elements in the correct order.

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 69% (9+ million submissions).

Typical patterns to solve this problem:

• Linked List
• Recursion

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 function implements an in-place merge of two sorted singly-linked lists. It returns a pointer to the head of a new list that preserves the sorted order without allocating additional nodes. The algorithm proceeds by first handling empty inputs, then establishing the initial head, and finally iterating through both lists, linking the smaller node at each step until one list is exhausted. At that point the remainder of the other list is attached directly.

Key Steps

Handling Empty Inputs

The first two conditional blocks detect whether either input list is empty. If the first list is null, the function returns the second list unchanged; if the second list is null, it returns the first list unchanged. This early exit eliminates unnecessary processing when one list contains no elements.

if (!list1)
    return list2;
if (!list2)
    return list1;

Selecting the Initial Head

A temporary pointer result is used to store the head of the merged list. The code compares the values at the current heads of the two lists. The smaller node becomes the head, and the corresponding input pointer is advanced to its next node. This step establishes the starting point for the merged sequence.

ListNode* result = nullptr;
if (list1->val < list2->val)
{
    result = list1;
    list1 = list1->next;
}
else
{
    result = list2;
    list2 = list2->next;
}

Iterative Merging Loop

A pointer current tracks the last node attached to the merged list. Inside an infinite loop, the algorithm first checks whether either input list has been exhausted. If list1 is null, the remainder of list2 is linked to current->next and the merged list is returned. The symmetric case handles exhaustion of list2.

If both lists still contain nodes, the values are compared. The node with the smaller value is linked to current->next, and the corresponding input pointer is advanced. After linking, current itself moves forward to the newly attached node. This process repeats until one list runs out of nodes.

auto current = result;
while (true)
{
    if (!list1)
    {
        current->next = list2;
        return result;
    }
    if (!list2)
    {
        current->next = list1;
        return result;
    }

    if (list1->val < list2->val)
    {
        current->next = list1;
        list1 = list1->next;
    }
    else
    {
        current->next = list2;
        list2 = list2->next;
    }

    current = current->next;
}

Final Return

Although the loop contains return statements for all termination paths, a final return result; exists after the loop as a safeguard, ensuring the function always yields a pointer to the merged list.

return result;

Edge Cases Addressed

The implementation explicitly handles the scenario where one or both input lists are empty at the outset, returning the non-empty list or null as appropriate. During the merging process, the code detects when either list becomes empty and attaches the remaining nodes of the other list without further comparison. This guarantees correct behavior when the lists have unequal lengths, when one list contains all smaller elements, or when the lists consist of a single node each. The use of direct pointer reassignment ensures that the merged list correctly terminates with a null next pointer once all nodes have been linked.

Performance Optimizations

The algorithm operates entirely in place, reusing the existing nodes of the input lists. No auxiliary data structures or dynamic memory allocations are introduced, which minimizes overhead. By advancing the input pointers only after linking a node, the code avoids redundant traversals. Early exit conditions for empty inputs and for exhausted lists reduce the number of iterations required, especially when one list is significantly shorter than the other. The use of a single current pointer to track the tail of the merged list eliminates the need for repeated searches for the insertion point, resulting in a tight, constant-time per-node operation.

Imagine having two separate piles of numbered building blocks, where each pile is already sorted from the smallest number at the top to the biggest number at the bottom. This code acts like a helper who wants to put both of those piles into one single, long line of blocks while keeping the numbers in the correct order.

First, the helper looks at the two piles to see if one of them is already empty. If a pile has nothing, the helper just takes the other pile because it is already finished. If both have blocks, the helper looks at the very top block of each pile, picks the smaller one, and starts a new line with it.

Now the real work begins. The helper keeps looking at the top block of both piles, compares them, and chooses the smaller one to add to the end of the new line. As each block is picked, the helper moves forward to the next block in that specific pile. If one pile eventually runs out of blocks, the helper simply takes everything that is left in the other pile and attaches it to the end of the new line because those blocks are already in order. Once all the blocks are in one long line, the job is done.

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

Time: linear
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	AdelDaniel								Dart
	aylei					Rust
	begeekmyfriend				C
	BigEggStudy			C#
	black-shadows	C++
	bujosa					Rust
	chandansgowda		Python
	charles-wangkai						Java
	chenyanzhe	C++
	DimitrisJim				C
	everthis							JS
	fartem									Ruby
	FelixFan1122			C#
	fengvyi	C++
	fpdjsns	C++
	gaosq0604		Python
	halfrost											Go
	JoshCrozier							JS
	keineahnung2345	C++
	Krazune	C++
	lennylxx				C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	pruthvikp		Python
	qiyuangong		Python
	ruoru					Rust
	Shamik07								Dart
	shreymehul			C#
	sonugiri1043	C++
	suxrobGM			C#
	trung-hn		Python
	varunu28						Java
	vli02				C
	vthwang						Java
	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
AdelDaniel	Dart
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Rust
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
gaosq0604	Python
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
pruthvikp	Python
qiyuangong	Python
ruoru	Rust
Shamik07	Dart
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
vthwang	Java
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