Abstract / Summary

Reverse a portion of a linked list between two specified nodes by changing the direction of the links in that segment.

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

Typical patterns to solve this problem:

• Linked List

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 reverses a sub-section of a singly-linked list defined by the positions left and right. Rather than altering the node connections, it keeps the original link structure intact and achieves the reversal by swapping the values stored in the nodes that lie within the specified interval. This approach simplifies pointer management while still delivering the expected logical outcome of a sub-list reversal.

Key Steps

Locating the Start Node

The algorithm first advances a pointer from the head of the list to the node that corresponds to the left position. This is done with a simple loop that iterates left-1 times, moving the pointer forward each iteration.

start = head
for _ in range(left - 1):
    start = start.next

Collecting Values from the Target Segment

Once the start node is identified, the code gathers the values of all nodes from left through right inclusive. It stores these values in a temporary Python list, preserving their original order.

values = []
current = start
for _ in range(left, right + 1):
    values.append(current.val)
    current = current.next

Writing the Reversed Values Back

After the values have been collected, the algorithm iterates over the list in reverse order and writes each value back into the corresponding node, moving forward through the linked list as it goes. This effectively reverses the segment’s data without touching the node links.

current = start
for v in reversed(values):
    current.val = v
    current = current.next

Returning the Modified List

Finally, the method returns the original head reference, which now points to a list whose sub-segment between left and right appears reversed.

return head

Edge Cases Handled

When the interval to reverse consists of a single element (i.e., left equals right), the collection loop still runs but the reversed write-back loop writes the same single value back, leaving the list unchanged as expected.

If left is 1, the start pointer is positioned at the head itself, so the reversal begins from the very first node without requiring any special handling.

When right corresponds to the last node of the list, the collection loop proceeds until it reaches the terminal node, and the subsequent write-back loop stops precisely after processing that node, ensuring the tail element is correctly included in the reversal.

The algorithm also works correctly for lists of any length that contain at least right nodes, as the loops are bounded by the provided indices.

Performance Optimizations

By opting to swap node values rather than rewire the next pointers, the implementation avoids the overhead associated with pointer manipulation, such as updating multiple references and handling edge connections. This value-centric strategy reduces the number of structural changes to a constant factor regardless of the segment size.

The temporary list used to store the segment’s values is allocated only once and sized exactly to the number of nodes being reversed, which minimizes memory churn. The subsequent use of Python’s built-in reversed iterator provides an efficient way to traverse the collected values in reverse order without creating an additional copy.

Overall, the method performs the reversal with a small, predictable amount of work: a linear pass to locate the start, a linear pass to collect values, and a linear pass to write them back, all while keeping the underlying linked-list structure untouched.

Imagine a long train where each car is connected to the one behind it, and every car has a special number painted on its side. Sometimes it is fun to pick a section of the train and flip the order of the numbers on those specific cars.

The code starts by walking down the track to find the very first car that needs its number changed. Once it finds that spot, it looks at the numbers in all the cars from the start to the end of the section and puts those numbers into a little basket.

After all the numbers are safely stored in the basket, the code goes back to the beginning of that section. It picks up the numbers from the basket, but it takes them out in reverse order. It places the last number from the basket onto the first car in the section, the second to last number onto the next car, and so on until it reaches the end of the section. Now, the train looks exactly the same as before, but the numbers in that middle part have been swapped around.

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	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei					Rust
	begeekmyfriend							C
	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai			Java
	chenyanzhe	C++
	everthis						JS
	fartem								Ruby
	FelixFan1122				C#
	fengvyi	C++
	fpdjsns	C++
	gaosq0604		Python
	Garvit244		Python
	halfrost									Go
	haoel			Java
	JoshCrozier						JS
	keineahnung2345	C++
	lennylxx							C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	pruthvikp		Python
	qiyuangong		Python
	ruoru					Rust
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	trung-hn		Python
	varunu28			Java
	vthwang			Java
	wisdompeak	C++
	XiaotaoGuo	C++
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
gaosq0604	Python
Garvit244	Python
halfrost	Go
haoel	Java
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
pruthvikp	Python
qiyuangong	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
wisdompeak	C++
XiaotaoGuo	C++
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