Abstract / Summary

Given a linked list and an integer n remove the nth node from its end.

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 52% (8+ million submissions).

Typical patterns to solve this problem:

• Linked List
• Two Pointers

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 removeNthFromEnd method removes the n-th node from the end of a singly linked list and returns the possibly new head. It first determines the total length of the list, then uses that length to locate the node that precedes the target, adjusts the links, and finally returns the original head unless the removal affects the first element.

Key Steps

The algorithm begins by walking the list once to compute its length.

auto current = head;
auto length = 0;
while (current)
{
    length++;
    current = current->next;
}

After the length is known, several early-exit conditions are evaluated. If the list is empty (length == 0) the function returns nullptr. If the requested position exceeds the list size (n > length) the original head is returned unchanged. When the node to delete is the first one (n == length) the function returns head->next, effectively discarding the original head.

if (length == 0)
    return nullptr;
if (n >  length)
    return head;
if (n == length)
    return head->next;

When the removal target lies somewhere in the middle, the index of the predecessor is computed as pos = length - n. The traversal then starts from the second node, keeping a prev pointer that trails current. The loop decrements pos until it reaches the node just before the one to delete.

auto pos = length - n;

current = head->next;
auto prev = head;
while (pos-- > 1 && current)
{
    prev = current;
    current = current->next;
}

Finally, the link of the predecessor is rewired to skip the target node, and the original head is returned.

prev->next = current->next;
return head;

Edge Cases Handled

The implementation explicitly checks for an empty list, returning nullptr when no nodes exist. It also guards against a request for a position larger than the list length, leaving the list unchanged. When the node to be removed is the first element, the function returns the second node as the new head, thereby handling the head-removal scenario without additional pointer gymnastics. The loop condition && current ensures that traversal stops safely even if the computed position somehow reaches the end of the list, preventing dereferencing of a null pointer.

Performance Optimizations

The code performs a single pass to obtain the list length and a second, bounded pass to locate the predecessor of the node to delete. By calculating pos = length - n once, it avoids repeated arithmetic inside the loop. The early-exit checks eliminate unnecessary traversal when the removal target is at the head or when the request is invalid, saving work for those cases. The use of simple pointer assignments (prev->next = current->next) updates the list in constant time once the correct location is reached, keeping the overall work proportional to the length of the list.

Imagine a long train made of many little cars hooked together in a line. Each car is linked to the one behind it, and there is a person inside each car. This code is like a set of instructions for a conductor who wants to take away one specific car from that long line.

First, the conductor walks from the very front of the train all the way to the back to count every single car. This helps the conductor know exactly how long the train is. Once the total number of cars is known, the conductor figures out which car needs to be removed by counting backward from the very end.

After finding the right spot, the conductor walks along the train again, stopping just before the car that needs to disappear. To remove a car, the conductor makes a small change. The car right before the one being removed stops holding onto the target car and instead reaches out to grab onto the next car in line behind it. This leaves the unwanted car all by itself, effectively taking it out of the train, while the rest of the cars stay connected in a new, shorter line.

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	Java	C#	Rust		JS	Go	Ruby			PHP	Swift	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei					Rust
	begeekmyfriend						C
	BigEggStudy				C#
	black-shadows	C++
	bujosa					Rust
	chandansgowda		Python
	charles-wangkai			Java
	chenyanzhe	C++
	Dijkstra-Edu			Java
	everthis							JS
	fartem									Ruby
	FelixFan1122				C#
	fengvyi	C++
	gaosq0604		Python
	Garvit244		Python
	halfrost								Go
	haoel	C++
	JoshCrozier							JS
	keineahnung2345	C++
	lennylxx						C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	muhammadfarhankt								Go
	pruthvikp		Python
	qiyuangong			Java
	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, Swift, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Rust
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	Java
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
gaosq0604	Python
Garvit244	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
muhammadfarhankt	Go
pruthvikp	Python
qiyuangong	Java
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