What is the brute force approach and complexity for Rotate List?

Repeat k % n times: walk to the last node and move it to the front with time complexity O(n · (k % n)) and space complexity O(1).

What is the optimal approach and complexity for Rotate List?

Count n, join the tail to the head, walk n − k%n − 1 steps and cut with optimal time complexity O(n) and space complexity O(1).

How do you identify the pattern for Rotate List?

Look for key signals in the prompt: "rotate the list to the right by k" indicates The tail wraps around to the front → join the tail to the head to make a circle, then cut it.; "k can be bigger than the length" indicates A full turn changes nothing → use k % n, never k itself.; "singly linked list, return the new head" indicates Only one link changes → relink nodes, no copying of values..

Rotate List

Medium·LeetCode #61Basic Reinforcement

LeetCode

Jump:

30-Second Mental ModelLinked List — Reordering / rotation (close the circle, cut once)

Complexity:O(n · (k % n))→O(n)

Key Insight

Shifting right by s (where s = k % n) is the same as cutting the list at one place. Count the nodes and find the tail. Join the tail to the head to make a circle. A circle has no start, so cut it once, right after the node that will end the new list. Shifting the circle changes nothing except where you cut it.

Core Validity Invariant

The answer is the circle read from the node n − (k % n) steps from the old head, with the link just before that node cut.

Problem

You are given the head of a singly linked list and a number k. Move the list k places to the right. Each shift takes the last node and puts it at the front. Return the new head.

The list is changed by relinking nodes. Do not copy values into new nodes.

Input

head, the first node of a singly linked list (it can be empty), and k, a number that is zero or more.

Output

The head of the rotated list.

Example 1

Input: head = [1, 2, 3, 4, 5], k = 2

Output: [4, 5, 1, 2, 3]

Two shifts: first 5 moves to the front, then 4 does. The last two nodes end up at the front.

Example 2

Input: head = [0, 1, 2], k = 4

Output: [2, 0, 1]

There are only 3 nodes. Three shifts give the same list back, so 4 shifts is the same as 1 shift: 2 moves to the front.

Constraints

• The list has between 0 and 500 nodes.
• -100 ≤ Node.val ≤ 100
• 0 ≤ k ≤ 2 × 10^9

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If k = 1, which node becomes the new head? What about k = 2?
2.
What happens when k is bigger than the number of nodes? Do I really need to shift that many times?
3.
Where does the new head sit, counting from the old head? Can I find that spot with one walk?
4.
If I join the tail back to the head, what shape does the list have? Where would I cut it?
5.
When k is an exact multiple of the length, what should the answer look like?

Brute force approach

Idea

A right shift by one is easy to picture: the last node jumps to the front. Repeat that k times. Since k can be huge, only k % n shifts matter. Doing them one at a time means walking the whole list again for every shift.

Thinking process

1
Rotating right by one: the last node moves to the front.
2
Do that k times. That is the rule written out, so it is the natural first idea. On [1, 2, 3, 4, 5] with k = 2: the first shift gives 5 → 1 → 2 → 3 → 4, and the second gives 4 → 5 → 1 → 2 → 3, which is the answer.
3
Each shift needs the node before the last one, so each shift walks the whole list again.
4
A full turn of n shifts changes nothing, so stop after k % n shifts. Check on [0, 1, 2], k = 4: n = 3 and k % n = 1. One shift moves 2 to the front and gives 2 → 0 → 1, the same as four shifts.

Visual

Each cell is a node in `next` order, left → right, and `null` is the end. Blue = the node walking (last) and the one before it (prev). Purple = the node just moved to the front. Every shift starts a new walk from the head, so the same nodes are visited again and again.

One node per shift, walking every timehead = [1, 2, 3, 4, 5], k = 7step 1/11

list

null

Work so far

shifts: 0 of 2
node visits: 0

We must shift 2 time(s), since 7 % 5 = 2

Each shift walks the whole list to find the last node and the node before it. Nothing has moved yet.

Code & Implementation

brute.cpp

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == nullptr || head->next == nullptr) return head;
        // Count the nodes. Rotating by n steps brings the list back to where it started.
        int n = 0;
        for (ListNode* cur = head; cur != nullptr; cur = cur->next) n++;
        int shifts = k % n;
        // One step: unhook the last node and put it in front of the head.
        for (int step = 0; step < shifts; step++) {
            ListNode* prev = nullptr;
            ListNode* last = head;
            while (last->next != nullptr) {   // walk the whole list again every step
                prev = last;
                last = last->next;
            }
            prev->next = nullptr;
            last->next = head;
            head = last;
        }
        return head;
    }
};

import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) return head;
        // Count the nodes. Rotating by n steps brings the list back to where it started.
        int n = 0;
        for (ListNode cur = head; cur != null; cur = cur.next) n++;
        int shifts = k % n;
        // One step: unhook the last node and put it in front of the head.
        for (int step = 0; step < shifts; step++) {
            ListNode prev = null;
            ListNode last = head;
            while (last.next != null) {   // walk the whole list again every step
                prev = last;
                last = last.next;
            }
            prev.next = null;
            last.next = head;
            head = last;
        }
        return head;
    }
}

from typing import Optional, List, Dict, Tuple

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        # Count the nodes. Rotating by n steps brings the list back to where it started.
        n = 0
        cur = head
        while cur:
            n += 1
            cur = cur.next
        shifts = k % n
        # One step: unhook the last node and put it in front of the head.
        for _ in range(shifts):
            prev = None
            last = head
            while last.next:   # walk the whole list again every step
                prev = last
                last = last.next
            if prev:
                prev.next = None
            last.next = head
            head = last
        return head

export class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.next = (next === undefined ? null : next);
    }
}

export function rotateRight(head: ListNode | null, k: number): ListNode | null {
    if (head === null || head.next === null) return head;
    // Count the nodes. Rotating by n steps brings the list back to where it started.
    let n = 0;
    for (let cur: ListNode | null = head; cur !== null; cur = cur.next) n++;
    const shifts = k % n;
    // One step: unhook the last node and put it in front of the head.
    for (let step = 0; step < shifts; step++) {
        let prev: ListNode | null = null;
        let last: ListNode = head;
        while (last.next !== null) {   // walk the whole list again every step
            prev = last;
            last = last.next;
        }
        if (prev !== null) prev.next = null;
        last.next = head;
        head = last;
    }
    return head;
}

Complexity

Time O(n · (k % n))Space O(1)

Each shift walks the whole list. When k % n is close to n, that is about n² steps. Every shift repeats the same walk the previous shift just did.

Optimized approach

Idea

Start from brute force

The brute force moves one node per shift, so every shift walks the whole list again to find the last two nodes.

Find the repeated work

Each shift repeats the same walk to the end. But shifting right by s moves the last s nodes to the front in one go, and that is the same as cutting a circle once.

Define the state — what variables do I need?

n: The number of nodes. We need it to turn k into k % n.
tail: The last node. It gets joined to the head to make the circle.
newTail: The node that ends the new list. It is n − (k % n) − 1 steps from the old head.
newHead: newTail->next, the first node of the answer.

Define validity

The answer is the circle read from the node n − (k % n) steps from the old head, with the link just before that node cut.

Define the transitions — when does each pointer move, and why is it safe?

Pass 1: count and find the tail

walk from head, adding 1 to n for each node, and stop on the last node

We need n to turn k into k % n, and the tail to close the circle. Both come from one walk.

k % n is 0

return head

A full turn leaves the list unchanged, so there is nothing to cut.

Close the circle

tail->next = head

Every node now has a next, so the cut can be made at any spot. The join between old tail and old head is already right.

Walk to the new tail

newTail = head, then walk n − shift − 1 steps

newTail is one node before the new head, and the new head is n − shift nodes from the old head.

Cut

newHead = newTail->next; newTail->next = nullptr

This breaks the circle at exactly one link. The new tail now ends the list, so no cycle is left.

What does the current window add to the answer?

Each node in the answer is the same node as before, just reached in a new order. The cut position decides which nodes move to the front.

Code & Implementation

optimal.cpp

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == nullptr || head->next == nullptr) return head;
        // Pass 1: count the nodes and find the tail.
        ListNode* tail = head;
        int n = 1;
        while (tail->next != nullptr) {
            tail = tail->next;
            n++;
        }
        // k can be bigger than n, and a multiple of n changes nothing.
        int shift = k % n;
        if (shift == 0) return head;
        // Close the list into a circle. The new head is n - shift nodes from the
        // old head, so the new tail is the node just before it. Cut the link there.
        tail->next = head;
        ListNode* newTail = head;
        for (int i = 0; i < n - shift - 1; i++) newTail = newTail->next;
        ListNode* newHead = newTail->next;
        newTail->next = nullptr;
        return newHead;
    }
};

import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) return head;
        // Pass 1: count the nodes and find the tail.
        ListNode tail = head;
        int n = 1;
        while (tail.next != null) {
            tail = tail.next;
            n++;
        }
        // k can be bigger than n, and a multiple of n changes nothing.
        int shift = k % n;
        if (shift == 0) return head;
        // Close the list into a circle. The new head is n - shift nodes from the
        // old head, so the new tail is the node just before it. Cut the link there.
        tail.next = head;
        ListNode newTail = head;
        for (int i = 0; i < n - shift - 1; i++) newTail = newTail.next;
        ListNode newHead = newTail.next;
        newTail.next = null;
        return newHead;
    }
}

from typing import Optional, List, Dict, Tuple

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        # Pass 1: count the nodes and find the tail.
        tail = head
        n = 1
        while tail.next:
            tail = tail.next
            n += 1
        # k can be bigger than n, and a multiple of n changes nothing.
        shift = k % n
        if shift == 0:
            return head
        # Close the list into a circle. The new head is n - shift nodes from the
        # old head, so the new tail is the node just before it. Cut the link there.
        tail.next = head
        new_tail = head
        for _ in range(n - shift - 1):
            if new_tail:
                new_tail = new_tail.next
        new_head = new_tail.next if new_tail else None
        if new_tail:
            new_tail.next = None
        return new_head

export class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.next = (next === undefined ? null : next);
    }
}

export function rotateRight(head: ListNode | null, k: number): ListNode | null {
    if (head === null || head.next === null) return head;
    // Pass 1: count the nodes and find the tail.
    let tail: ListNode = head;
    let n = 1;
    while (tail.next !== null) {
        tail = tail.next;
        n++;
    }
    // k can be bigger than n, and a multiple of n changes nothing.
    const shift = k % n;
    if (shift === 0) return head;
    // Close the list into a circle. The new head is n - shift nodes from the
    // old head, so the new tail is the node just before it. Cut the link there.
    tail.next = head;
    let newTail: ListNode = head;
    for (let i = 0; i < n - shift - 1; i++) newTail = newTail.next!;
    const newHead: ListNode | null = newTail.next;
    newTail.next = null;
    return newHead;
}

Complexity

Time O(n)Space O(1)

Pass 1 counts n and finds the tail, which is n steps. One more walk of at most n steps finds the cut. That is about 2n steps in total, and only a few pointers of extra memory.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Repeat k % n times: walk to the last node and move it to the front	O(n · (k % n))	O(1)
Optimal	Count n, join the tail to the head, walk n − k%n − 1 steps and cut	O(n)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“rotate the list to the right by k”The tail wraps around to the front → join the tail to the head to make a circle, then cut it.
“k can be bigger than the length”A full turn changes nothing → use k % n, never k itself.
“singly linked list, return the new head”Only one link changes → relink nodes, no copying of values.

singly linked list+tail joins head (circle)+cut after n − (k mod n) nodes→Linked List — Reordering / rotation (close the circle, cut once)

Reordering here means splitting one list at one point and putting the two parts in swapped order. Rotate List is the simplest reorder: one cut is enough. The join is a helper: it lets the cut land anywhere on the circle. Odd Even Linked List and Reorder List later need several relinks in turn, not just one join and one cut.

Don't make this mistake

Forgetting k % n when k is bigger than the list

✗ int steps = n - k; // k = 7, n = 5 gives -2

✓ int steps = n - k % n; // 7 % 5 = 2, so the new head is 3 steps from the old head

k can be far bigger than n, up to 2 × 10^9. A full turn changes nothing, so only k % n matters. Without it, the cut position is negative or past the end, and the answer is wrong or the program crashes.

Walking one node too far when k is a multiple of n

✗ tail->next = head; ListNode* newTail = head; for (int i = 0; i < n - k % n; i++) newTail = newTail->next; // k % n == 0 walks n steps ListNode* newHead = newTail->next; newTail->next = nullptr;

✓ if (k % n == 0) return head; // a full turn changes nothing tail->next = head; // ... then walk n - k % n - 1 steps

When k % n is 0, the loop walks one node too far. newTail lands on the old head, so the answer comes out shifted by one (2 3 4 5 1 for k = 5). Check for the zero case before cutting.

Shifting like an array, one step per k

✗ for (int i = 0; i < k; i++) { // walk to the last node, move it to the front }

✓ Count n once, close the circle, cut once.

Pattern confusion: an array can rotate by moving values in place, but a linked list rotates by moving one link. Repeating the array idea walks the whole list on every shift. On the dry run (1 → 2 → 3 → 4 → 5, k = 7), this loop does 7 shifts, and each one walks all 5 nodes: 35 steps. Only 7 % 5 = 2 shifts change the answer, and the one-pass plan takes 7 node visits (5 to count, 2 to reach the cut). With k near 2 × 10^9 the loop is far too slow.

Forgetting to cut the circle

✗ tail->next = head; ListNode* newTail = head; for (int i = 0; i < n - k % n - 1; i++) newTail = newTail->next; return newTail->next; // the list still loops back to the head

✓ ListNode* newHead = newTail->next; newTail->next = nullptr; // cut here return newHead;

Joining the tail to the head makes a circle. If you return without cutting the link after newTail, the list never ends, and any traversal loops forever. The cut is a required link change, not an optional step.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Linked List — Reversal translate into production architectures and low-level memory mechanics.

LLD Architecture