Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Rotate List

MEDIUMProblemSolveExternal Links

Description

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

Rotating to the right by one place means the last node of the list moves to the front and becomes the new head. Rotating by k places means repeating this operation k times.

For example, if the list is 1 → 2 → 3 → 4 → 5 and k = 2, then after two right rotations, the list becomes 4 → 5 → 1 → 2 → 3. The last two nodes (4 and 5) moved to the front.

Note that k can be very large — even larger than the length of the list. In that case, the list effectively wraps around multiple times, and only the remainder matters.

Examples

Example 1

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

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

Explanation: After the first right rotation, the last element (5) moves to the front: 5 → 1 → 2 → 3 → 4. After the second right rotation, the last element (4) moves to the front: 4 → 5 → 1 → 2 → 3. The final result is [4, 5, 1, 2, 3].

Example 2

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

Output: [2, 0, 1]

Explanation: The list has 3 nodes. Rotating right by 3 places returns the list to its original state: [0, 1, 2]. So rotating by 4 places is the same as rotating by 4 % 3 = 1 place. One right rotation moves the last element (2) to the front: 2 → 0 → 1.

Example 3

Input: head = [], k = 0

Output: []

Explanation: An empty list stays empty regardless of how many rotations are performed.

Constraints

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

Editorial

Brute Force

Intuition

The most straightforward way to rotate a list to the right by k places is to literally perform the rotation one step at a time, k times. In each single rotation, we move the last node of the list to the front.

To move the last node to the front, we need to:

  1. Find the second-to-last node by traversing the list.
  2. Detach the last node from the second-to-last node.
  3. Make the last node point to the current head.
  4. Update the head to be the last node.

Think of it like a circular conveyor belt of items. To rotate right by one, you take the item at the end and place it at the beginning. Do this k times and you get the desired rotation.

However, since k can be as large as 2 × 10^9, doing this literally for every rotation would be extremely slow for large k. But this is the most intuitive starting point.

Step-by-Step Explanation

Let's trace through with head = [1, 2, 3, 4, 5], k = 2:

Rotation 1:

Step 1: Traverse to find the second-to-last node.

  • Start at node(1), move to node(2), node(3), node(4). Node(4) is second-to-last because node(4).next = node(5) and node(5).next = null.

Step 2: Detach node(5) from node(4).

  • Set node(4).next = null.
  • last = node(5).

Step 3: Move node(5) to the front.

  • Set node(5).next = head (which is node(1)).
  • Update head = node(5).
  • List is now: 5 → 1 → 2 → 3 → 4.

Rotation 2:

Step 4: Traverse to find the second-to-last node.

  • Start at node(5), move through 1, 2, 3. Node(3) is second-to-last.

Step 5: Detach node(4) from node(3).

  • Set node(3).next = null.
  • last = node(4).

Step 6: Move node(4) to the front.

  • Set node(4).next = head (which is node(5)).
  • Update head = node(4).
  • List is now: 4 → 5 → 1 → 2 → 3.

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

Brute Force — Moving Last Node to Front, One Rotation at a Time — Watch how we perform two separate rotations, each time traversing to the end to detach the last node and move it to the front of the list.

Algorithm

  1. Handle edge cases: if head is null, head.next is null, or k is 0, return head as-is
  2. Repeat k times:
    a. Traverse the list to find the second-to-last node (the node whose next's next is null)
    b. Save a reference to the last node
    c. Disconnect the last node from the second-to-last node (set secondToLast.next = null)
    d. Point the last node's next to the current head
    e. Update head to be the last node
  3. Return the new head

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == nullptr || head->next == nullptr || k == 0) {
            return head;
        }
        
        // Find length to reduce k
        int len = 0;
        ListNode* curr = head;
        while (curr != nullptr) {
            len++;
            curr = curr->next;
        }
        k = k % len;
        
        // Perform k rotations
        for (int i = 0; i < k; i++) {
            // Find second-to-last node
            ListNode* prev = head;
            while (prev->next->next != nullptr) {
                prev = prev->next;
            }
            ListNode* last = prev->next;
            prev->next = nullptr;
            last->next = head;
            head = last;
        }
        
        return head;
    }
};
# Definition for singly-linked list.
# 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 or k == 0:
            return head
        
        # Find length to reduce k
        length = 0
        curr = head
        while curr:
            length += 1
            curr = curr.next
        k = k % length
        
        # Perform k rotations
        for _ in range(k):
            # Find second-to-last node
            prev = head
            while prev.next.next:
                prev = prev.next
            last = prev.next
            prev.next = None
            last.next = head
            head = last
        
        return head
/**
 * Definition for singly-linked list.
 * public 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 || k == 0) {
            return head;
        }
        
        // Find length to reduce k
        int len = 0;
        ListNode curr = head;
        while (curr != null) {
            len++;
            curr = curr.next;
        }
        k = k % len;
        
        // Perform k rotations
        for (int i = 0; i < k; i++) {
            ListNode prev = head;
            while (prev.next.next != null) {
                prev = prev.next;
            }
            ListNode last = prev.next;
            prev.next = null;
            last.next = head;
            head = last;
        }
        
        return head;
    }
}

Complexity Analysis

Time Complexity: O(n × k)

For each of the k rotations, we traverse the entire list of n nodes to find the second-to-last node. After reducing k to k % n, the worst case is k = n - 1, giving O(n × (n-1)) = O(n²).

Space Complexity: O(1)

We only use a constant number of pointer variables (prev, last, curr). No extra data structures are created.

Why This Approach Is Not Efficient

The brute force approach performs k separate traversals of the list, giving O(n × k) time in the worst case (O(n²) after reducing k modulo n). Each rotation redundantly walks the entire list just to move one node.

The core inefficiency is that we're doing the same work over and over: finding the end of the list. But the structure of the rotation tells us something powerful — rotating right by k is equivalent to taking the last k nodes and moving them all to the front as a group.

The key insight is: if we know the length n and reduce k to k % n, then rotating right by k is the same as making the (n - k)th node the new tail and the (n - k + 1)th node the new head. We can find this split point in a single traversal and rearrange the pointers in O(1) — no need to move nodes one at a time.

We need an approach that does this in a single pass rather than k passes.

Optimal Approach - Circular Link and Break

Intuition

Instead of moving nodes one at a time, we can view the entire rotation as a single cut-and-reconnect operation.

Here is the key observation: rotating a list of length n to the right by k positions is the same as:

  1. Making the list circular (connect the tail to the head)
  2. Finding the new tail at position (n - k % n - 1) from the start
  3. The new head is right after the new tail
  4. Breaking the circle at that point

Imagine a necklace of beads laid in a circle. No matter how you "rotate" it, the beads stay in the same circular order — all that changes is where you cut the necklace to lay it flat again. So we first join the ends to make a circle, then cut at the correct spot.

For example, with [1, 2, 3, 4, 5] and k = 2:

  • Length n = 5, k % n = 2
  • New tail position = n - k - 1 = 5 - 2 - 1 = 2 (0-indexed), which is node(3)
  • New head = node(3).next = node(4)
  • Break the link: node(3).next = null
  • Result: 4 → 5 → 1 → 2 → 3

This requires only one and a half traversals of the list and O(1) space.

Step-by-Step Explanation

Let's trace through with head = [1, 2, 3, 4, 5], k = 2:

Step 1: Traverse the list to find the length and the tail node.

  • Visit 1, 2, 3, 4, 5. Length n = 5. Tail is node(5).

Step 2: Reduce k: k = 2 % 5 = 2. Since k ≠ 0, we need to rotate.

Step 3: Make the list circular.

  • Set tail.next = head: node(5).next = node(1).
  • The list is now a circle: 1 → 2 → 3 → 4 → 5 → 1 → 2 → ...

Step 4: Find the new tail position.

  • Steps to walk from current head: n - k - 1 = 5 - 2 - 1 = 2 steps.
  • Start at node(1), move 1 step → node(2), move 2 steps → node(3).
  • New tail = node(3).

Step 5: Set the new head.

  • New head = newTail.next = node(3).next = node(4).

Step 6: Break the circle.

  • Set node(3).next = null.
  • List: 4 → 5 → 1 → 2 → 3.

Step 7: Return node(4) as the new head. Result: [4, 5, 1, 2, 3].

Optimal — Circular Link, Walk, and Break — Watch how we connect the tail to the head to form a circle, walk to the new break point, and cut the circle to produce the rotated list in a single pass.

Algorithm

  1. Handle edge cases: if head is null, head.next is null, or k is 0, return head.
  2. Traverse the list to find the length n and the tail node.
  3. Reduce k: set k = k % n. If k becomes 0, no rotation is needed — return head.
  4. Make the list circular: set tail.next = head.
  5. Walk (n - k - 1) steps from the head to find the new tail.
  6. Set the new head: newHead = newTail.next.
  7. Break the circle: set newTail.next = null.
  8. Return newHead.

Code

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == nullptr || head->next == nullptr || k == 0) {
            return head;
        }
        
        // Find the length and the tail
        int n = 1;
        ListNode* tail = head;
        while (tail->next != nullptr) {
            tail = tail->next;
            n++;
        }
        
        // Reduce k
        k = k % n;
        if (k == 0) return head;
        
        // Make the list circular
        tail->next = head;
        
        // Walk (n - k - 1) steps from head to find new tail
        ListNode* newTail = head;
        for (int i = 0; i < n - k - 1; i++) {
            newTail = newTail->next;
        }
        
        // Set new head and break circle
        ListNode* newHead = newTail->next;
        newTail->next = nullptr;
        
        return newHead;
    }
};
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or not head.next or k == 0:
            return head
        
        # Find the length and the tail
        n = 1
        tail = head
        while tail.next:
            tail = tail.next
            n += 1
        
        # Reduce k
        k = k % n
        if k == 0:
            return head
        
        # Make the list circular
        tail.next = head
        
        # Walk (n - k - 1) steps from head to find new tail
        new_tail = head
        for _ in range(n - k - 1):
            new_tail = new_tail.next
        
        # Set new head and break circle
        new_head = new_tail.next
        new_tail.next = None
        
        return new_head
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        
        // Find the length and the tail
        int n = 1;
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
            n++;
        }
        
        // Reduce k
        k = k % n;
        if (k == 0) return head;
        
        // Make the list circular
        tail.next = head;
        
        // Walk (n - k - 1) steps from head to find new tail
        ListNode newTail = head;
        for (int i = 0; i < n - k - 1; i++) {
            newTail = newTail.next;
        }
        
        // Set new head and break circle
        ListNode newHead = newTail.next;
        newTail.next = null;
        
        return newHead;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the list once to find its length and tail: O(n). Then we walk at most (n - 1) more steps to find the new tail: O(n). Total: O(n) + O(n) = O(n). Crucially, the time does not depend on k at all — we reduce k to k % n first.

Space Complexity: O(1)

We use only a constant number of pointer variables (tail, newTail, newHead). No auxiliary data structures are created regardless of input size.