Log inSign up
mediumLeetCodeNot Started

Rotate List

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Linked List
Solve on LeetCode
Lesson

Problem Statement

Given the head of a linked list, rotate the list to the right by k places.

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]
Explanation: Rotate 1 step: [5,1,2,3,4]. Rotate 2 steps: [4,5,1,2,3].

Example 2:

Input: head = [0,1,2], k = 4
Output: [2,0,1]
Explanation: Length = 3. k = 4 % 3 = 1 step rotation: [2,0,1].

Constraints:

  • The number of nodes in the list is in the range [0, 500].
  • -100 <= Node.val <= 100
  • 0 <= k <= 2 * 10^9

1. Simulation: Rotate One Step k Times

Intuition

1. If list length <= 1, return head. 2. Repeat k times: - Traverse list to find prev (second to last node) and tail (last node). - prev.next = null. - tail.next = head. - head = tail. 3. Return head.

When to apply: Conceptual explanation for small k values.

Algorithm

  1. Loop k times.
  2. Traverse to penultimate node.
  3. Move tail node to the front.
  4. Update head pointer.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct ListNode {
4 int val;
5 ListNode *next;
6 ListNode() : val(0), next(nullptr) {}
7 ListNode(int x) : val(x), next(nullptr) {}
8 ListNode(int x, ListNode *next) : val(x), next(next) {}
9};
10
11class Solution {
12public:
13 ListNode* rotateRight(ListNode* head, int k) {
14 if (!head || !head->next || k == 0) return head;
15
16 // Calculate length first to reduce k
17 int len = 0;
18 ListNode* curr = head;
19 while (curr) {
20 len++;
21 curr = curr->next;
22 }
23 k %= len;
24
25 for (int i = 0; i < k; ++i) {
26 ListNode* prev = nullptr;
27 ListNode* tail = head;
28 while (tail->next != nullptr) {
29 prev = tail;
30 tail = tail->next;
31 }
32 prev->next = nullptr;
33 tail->next = head;
34 head = tail;
35 }
36 return head;
37 }
38};
39
40int main() {
41 ListNode* head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
42 Solution sol;
43 ListNode* res = sol.rotateRight(head, 2);
44 while (res != nullptr) {
45 std::cout << res->val << " ";
46 res = res->next;
47 }
48 std::cout << std::endl;
49 return 0;
50}

Time & Space Complexity

  • Time complexity: O(k * N) — Traverses the list of length N for each of the k rotations, taking O(k * N) time (fails for k = 2 * 109).
  • Space complexity: O(1) — Only requires pointer manipulations: O(1) space.

2. Array Offset Transformation & List Reconstruction

Intuition

1. Collect all node values into an array vals of length N. 2. Compute k = k % N. 3. Create a rotated array rotated[ (i + k) % N ] = vals[i]. 4. Traverse the linked list and update curr.val with rotated[i].

When to apply: When modifying node values or creating a new list using standard array rotation techniques.

Algorithm

  1. Extract all node values to array.
  2. Compute rotated array positions using modular arithmetic.
  3. Overwrite linked list node values with rotated elements.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4struct ListNode {
5 int val;
6 ListNode *next;
7 ListNode() : val(0), next(nullptr) {}
8 ListNode(int x) : val(x), next(nullptr) {}
9 ListNode(int x, ListNode *next) : val(x), next(next) {}
10};
11
12class Solution {
13public:
14 ListNode* rotateRight(ListNode* head, int k) {
15 if (!head || !head->next || k == 0) return head;
16
17 std::vector<int> vals;
18 ListNode* curr = head;
19 while (curr != nullptr) {
20 vals.push_back(curr->val);
21 curr = curr->next;
22 }
23
24 int n = vals.size();
25 k %= n;
26 if (k == 0) return head;
27
28 std::vector<int> rotated(n);
29 for (int i = 0; i < n; ++i) {
30 rotated[(i + k) % n] = vals[i];
31 }
32
33 curr = head;
34 for (int v : rotated) {
35 curr->val = v;
36 curr = curr->next;
37 }
38 return head;
39 }
40};
41
42int main() {
43 ListNode* head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
44 Solution sol;
45 ListNode* res = sol.rotateRight(head, 2);
46 while (res != nullptr) {
47 std::cout << res->val << " ";
48 res = res->next;
49 }
50 std::cout << std::endl;
51 return 0;
52}

Time & Space Complexity

  • Time complexity: O(N) — Pass 1 extracts values in O(N), rotation takes O(N), and pass 2 updates values in O(N).
  • Space complexity: O(N) — Requires O(N) extra array memory to store values.

3. Circular Ring Formation & Cut at (N - k % N)

Intuition

1. If head == null || head.next == null || k == 0, return head. 2. Traverse to the tail of the list while counting the length N. 3. Compute effective shift: k = k % N. If k == 0, return head. 4. Connect tail.next = head forming a circular loop. 5. Advance stepsToNewTail = N - k steps from tail. 6. Let newTail be the node reached, and newHead = newTail.next. 7. Disconnect the circle: newTail.next = null. 8. Return newHead.

When to apply: The definitive, optimal O(N) time and O(1) space algorithm expected in coding interviews.

Algorithm

  1. Traverse to tail and count length N.
  2. If k % N == 0, return head.
  3. Connect tail.next = head (form circular list).
  4. Advance (N - (k % N)) steps from tail to reach new tail.
  5. Set newHead = newTail.next and newTail.next = null.
  6. Return newHead.

Linked List Interactive Dry Run

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Steps to new tail = N - (k % N) = 5 - 2 = 3 steps from dummy/tail
Visual state
Values and pointers at this exact step
linked list
This linked list trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Why this step matters

Steps to new tail = N - (k % N) = 5 - 2 = 3 steps from dummy/tail.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct ListNode {
4 int val;
5 ListNode *next;
6 ListNode() : val(0), next(nullptr) {}
7 ListNode(int x) : val(x), next(nullptr) {}
8 ListNode(int x, ListNode *next) : val(x), next(next) {}
9};
10
11class Solution {
12public:
13 ListNode* rotateRight(ListNode* head, int k) {
14 if (!head || !head->next || k == 0) return head;
15
16 // Step 1: Count length and locate tail
17 int length = 1;
18 ListNode* tail = head;
19 while (tail->next != nullptr) {
20 tail = tail->next;
21 length++;
22 }
23
24 // Step 2: Calculate effective rotation
25 k %= length;
26 if (k == 0) return head;
27
28 // Step 3: Form circular list
29 tail->next = head;
30
31 // Step 4: Advance to new tail
32 int stepsToNewTail = length - k;
33 ListNode* newTail = tail;
34 while (stepsToNewTail > 0) {
35 newTail = newTail->next;
36 stepsToNewTail--;
37 }
38
39 // Step 5: Sever circular ring
40 ListNode* newHead = newTail->next;
41 newTail->next = nullptr;
42
43 return newHead;
44 }
45};
46
47int main() {
48 ListNode* head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
49 Solution sol;
50 ListNode* res = sol.rotateRight(head, 2);
51 while (res != nullptr) {
52 std::cout << res->val << " ";
53 res = res->next;
54 }
55 std::cout << std::endl;
56 return 0;
57}

Time & Space Complexity

  • Time complexity: O(N) — Counting length takes N steps; advancing to new tail takes at most N steps. Total time is <= 2N = O(N).
  • Space complexity: O(1) auxiliary — Only a constant number of pointer variables are used: strict O(1) auxiliary memory.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Simulation: Rotate One Step k TimesO(k * N)O(1)Simulate rotating right by 1 position k times: locate second-to-last node, detach last node, and insert it at the head.High time complexity
2.Array Offset Transformation & List ReconstructionO(N)O(N)Extract node values into an array, apply circular index shifting (i + k) % N, and rewrite the values back into the list.—
3.Circular Ring Formation & Cut at (N - k % N)OptimalO(N)O(1) auxiliaryConnect tail to head to form a closed ring. Find the new tail at position (N - (k % N)), save newHead = newTail.next, and cut the ring (newTail.next = null).—

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Failing to reduce k %= length, resulting in Time Limit Exceeded when k is up to 2 * 109.

Pitfall 2:

Off-by-one in finding the new tail: starting the traversal from head requires length - k - 1 steps, whereas starting from tail requires length - k steps.

Pitfall 3:

Not handling empty list (head == null) or single node list (head.next == null).

Back to DSA Sheet