Abstract / Summary

Given the head of a linked list and positions k and n rotate the list to the right by k places.

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 43% (4+ 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 implementation provides a method to rotate a singly-linked list to the right by k positions. It first safeguards against trivial inputs, then determines the list’s length while locating its tail. By temporarily linking the tail back to the head, the list becomes circular, allowing the rotation offset to be applied with simple pointer arithmetic. Finally, the circular link is broken at the appropriate node, yielding the rotated list’s new head.

Key Steps

Handling empty list and zero rotation

if (!head)
    return nullptr;

if (k == 0)
    return head;

The early returns protect the algorithm from dereferencing a null pointer and avoid unnecessary work when no rotation is required.

Computing length and tail

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

A single traversal counts the nodes (length) and retains a reference to the last node (last). This information is essential for both normalizing the rotation count and forming the circular list.

Forming a circular list

last->next = head;

By pointing the original tail back to the head, the list becomes a closed loop. This transformation enables the rotation to be expressed as a simple shift within the circle.

Normalizing the rotation count

k %= length;
k = length - k;

The modulo operation reduces k to a value within the list’s size, handling cases where k exceeds the length. Subtracting the reduced k from the length converts the right-rotation problem into an equivalent left-shift, simplifying the subsequent traversal.

Locating the new tail

last = head;
while (--k > 0)
    last = last->next;

Starting from the original head, the loop advances k-1 steps to land on the node that will become the new tail after rotation.

Breaking the circle and returning the new head

auto result = last->next;
last->next = nullptr;
return result;

result captures the node following the new tail, which is the rotated list’s head. Setting last->next to nullptr restores the singly-linked structure, and the method returns the new head pointer.

Edge Cases Addressed

The code explicitly checks for a null head, returning nullptr to represent an empty list. When k equals zero, the original list is returned unchanged, avoiding any modifications. The modulo operation (k %= length) ensures that rotation counts larger than the list length are effectively reduced, so a request to rotate by a multiple of the length yields the original ordering. For a single-node list, the length calculation yields one, the modulo reduces any k to zero, and the subsequent subtraction results in k = 1 - 0 = 1. The loop that moves last executes zero times, leaving last at the sole node; breaking the circular link restores the original single-node list, which is the correct rotated result.

Performance Optimizations

The algorithm accomplishes its work with only two passes over the list: the first pass simultaneously determines the length and captures the tail, eliminating the need for a separate length-counting traversal. Forming a circular list avoids allocating additional nodes or auxiliary data structures, keeping memory usage constant. Normalizing k with a modulo operation prevents unnecessary full-cycle rotations, ensuring that the subsequent pointer movement is bounded by the list size. By reusing the last pointer for both tail identification and new-tail location, the code minimizes variable overhead and keeps the pointer arithmetic tight. Overall, the method achieves the rotation with minimal traversals and without extra storage.

Imagine a train made of little toy cars all hooked together in a line. The class is a way to describe how that train works. The code starts by checking if the train is empty. If there is no train, there is nothing to rotate. If the train has cars, the code counts how many cars there are by walking from the front all the way to the very last car.

Once it knows how many cars there are, it connects the last car to the first car to make a big circle. Because spinning a circle of cars a lot is the same as just spinning it a little, the code does some quick math to find out exactly where the new front of the train should be. It moves along the circle until it finds that spot. After it reaches the right place, it unhooks the cars to turn the circle back into a straight line again. The car after the one it stopped at becomes the new front of the train.

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