The challenge
Rotate a list to the right by k positions and return its new head.
k is a nonnegative integer; an empty list remains empty.
Example
[1, 2, 3, 4, 5], k = 2 → [4, 5, 1, 2, 3].
Use the walkthrough below to inspect the input and each state change.
See Rotate right, step by step
Follow the pointers. Watch each link change.
A1Inspect node links
| Node | Value | Next |
|---|---|---|
| A1 | 1 | A2 |
| A2 | 2 | A3 |
| A3 | 3 | A4 |
| A4 | 4 | A5 |
| A5 | 5 | null |
Read the input
IDs label node objects. Equal values can belong to different nodes. Solid arrows are next links; dashed arrows are random links.
Start from the input head pointers.View original input
A: 1 (A1) → 2 (A2) → 3 (A3) → 4 (A4) → 5 (A5); parameters: {"k":2}
Parameter indices are zero-based, except n from the end, which is one-based. Node IDs remain fixed when links change.
Put it into code
Only k modulo length matters. The new tail is length − k − 1 steps from head.
Node stores val and next; the random-pointer lesson adds random. C++ uses C++17 or later.
class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def rotate_right(head, k):
if head is None or head.next is None:
return head
tail, length = head, 1
while tail.next:
tail = tail.next
length += 1
k %= length
if k == 0:
return head
tail.next = head
new_tail = head
for _ in range(length - k - 1):
new_tail = new_tail.next
new_head = new_tail.next
new_tail.next = None
return new_head
#include <cstddef>
struct Node {
int val;
Node* next;
Node(int value = 0, Node* link = nullptr)
: val(value), next(link) {}
};
Node* rotate_right(Node* head, long long k) {
if (!head || !head->next) return head;
Node* tail = head;
long long length = 1;
while (tail->next) {
tail = tail->next;
++length;
}
k %= length;
if (k == 0) return head;
tail->next = head;
Node* new_tail = head;
for (long long i = 0; i < length - k - 1; ++i)
new_tail = new_tail->next;
Node* new_head = new_tail->next;
new_tail->next = nullptr;
return new_head;
}