# Rotate List
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/rotate-list)
Canonical: https://scaleengineer.com/dsa/problems/rotate-list
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Linked List
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Oracle](https://scaleengineer.com/companies/oracle), [Siemens](https://scaleengineer.com/companies/siemens), [Yahoo](https://scaleengineer.com/companies/yahoo)
---
## Problem
Given the `head` of a linked list, rotate the list to the right by `k` places.

**Example 1:**

![](https://assets.glich.co/dsa/rotate-list/image0.jpg) 

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

**Example 2:**

![](https://assets.glich.co/dsa/rotate-list/image1.jpg) 

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

**Constraints:**

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

# Approaches
## Brute Force: Rotate One by One
This approach simulates the rotation process directly. We rotate the list to the right by one position and repeat this operation `k` times. A key optimization is to first calculate the effective number of rotations, `k % n`, where `n` is the length of the list, to handle large values of `k`.
**Time:** O(n * (k % n)) · **Space:** O(1)
**Pros:** Conceptually simple and easy to understand.
**Cons:** Very inefficient, as it requires traversing the list `k` times.; Leads to Time Limit Exceeded on most platforms for large `k` or `n`.
### Explanation
The core idea is to perform the rotation one step at a time. To rotate the list to the right by one, we need to move the last element to the front. This involves finding the last and second-to-last nodes, making the last node the new head, and adjusting the pointers accordingly. This entire process is repeated `k` times.

To avoid unnecessary rotations when `k` is larger than the list length `n`, we first compute the effective number of rotations as `k' = k % n`. If `k'` is 0, the list remains unchanged. Otherwise, we perform the single-step rotation `k'` times.

Here is the algorithm:
1.  Handle edge cases: an empty list, a single-node list, or `k=0`.
2.  Calculate the list's length, `n`.
3.  Compute `k = k % n`. If `k` is 0, return the original list.
4.  Loop `k` times:
    a.  Find the last node and its predecessor (the second-to-last node).
    b.  Set the `next` of the second-to-last node to `null`.
    c.  Set the `next` of the last node to the current head.
    d.  Update the head to be the last node.
5.  Return the modified head.

```java
/**
 * 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 the length of the list
        int n = 1;
        ListNode current = head;
        while (current.next != null) {
            current = current.next;
            n++;
        }

        // Calculate effective rotations
        k = k % n;
        if (k == 0) {
            return head;
        }

        // Rotate k times
        for (int i = 0; i < k; i++) {
            ListNode last = head;
            ListNode secondLast = null;
            while (last.next != null) {
                secondLast = last;
                last = last.next;
            }
            
            if (secondLast != null) {
                secondLast.next = null;
                last.next = head;
                head = last;
            }
        }

        return head;
    }
}
```
### Algorithm
- If `head` is null, `head.next` is null, or `k` is 0, return `head`.
- Calculate the length of the list, `n`.
- Calculate `k = k % n`. If `k == 0`, return `head`.
- Repeat `k` times:
  - Traverse to the end of the list to find the last node (`last`) and the second-to-last node (`secondLast`).
  - Set `secondLast.next = null`.
  - Set `last.next = head`.
  - Update `head = last`.
- Return `head`.

## Optimal Approach: Make List Circular
This efficient approach avoids repeated traversals by first making the linked list circular. After determining the length `n`, we connect the tail to the head. Then, we calculate the position of the new tail, which is `n - (k % n) - 1` nodes from the beginning. We traverse to this new tail, break the link after it, and the next node becomes the new head.
**Time:** O(n) · **Space:** O(1)
**Pros:** Highly efficient with a time complexity linear to the list size.; Uses constant extra space.; Handles all edge cases including very large `k` values gracefully.
**Cons:** Temporarily modifies the list structure by making it circular, which might be a consideration in a multi-threaded environment without proper locking.
### Explanation
Instead of rotating one element at a time, we can solve this problem by rearranging pointers in a more direct way. The key insight is that rotating the list `k` times to the right is equivalent to taking the last `k` nodes and moving them to the front.

The steps are as follows:
1.  First, traverse the list to find its length, `n`, and its tail node. 
2.  Handle edge cases: if the list is empty, has one node, or `k` is 0, return the head.
3.  Calculate the effective rotations `k = k % n`. If `k` is 0, the list is unchanged, so we can return the head.
4.  Make the list circular by connecting the `next` pointer of the tail node to the head node.
5.  Now that we have a circular list, we need to find the new head and new tail. The last `k` nodes will form the new beginning of the list. This means the new tail is the node at position `n - k - 1` (0-indexed) from the original head.
6.  We traverse `n - k - 1` steps from the head to locate the `newTail`.
7.  The `newHead` is the node immediately following `newTail`.
8.  To finalize the new list, we break the circular link by setting `newTail.next` to `null`.
9.  Finally, we return the `newHead`.

```java
/**
 * 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;
        }

        // 1. Find the length and the tail node
        int n = 1;
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
            n++;
        }

        // Calculate effective rotations
        k = k % n;
        if (k == 0) {
            return head; // No rotation needed
        }

        // 2. Connect the tail to the head to form a circle
        tail.next = head;

        // 3. Find the new tail. It's at position (n - k - 1)
        int stepsToNewTail = n - k - 1;
        ListNode newTail = head;
        for (int i = 0; i < stepsToNewTail; i++) {
            newTail = newTail.next;
        }

        // 4. The new head is the node after the new tail
        ListNode newHead = newTail.next;

        // 5. Break the circle
        newTail.next = null;

        return newHead;
    }
}
```
### Algorithm
- Handle edge cases: if `head` is null, `head.next` is null, or `k` is 0, return `head`.
- Traverse the list to find its length `n` and the `tail` node.
- Calculate `k = k % n`. If `k == 0`, no rotation is needed, so return `head`.
- Make the list circular by setting `tail.next = head`.
- Calculate the position of the new tail: `steps = n - k - 1`.
- Traverse `steps` from the head to find the `newTail` node.
- The `newHead` is `newTail.next`.
- Break the circular link: `newTail.next = null`.
- Return `newHead`.

# Solutions
### CSharp

```csharp
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode RotateRight ( ListNode head , int k ) { if ( head == null || head . next == null ) { return head ; } var cur = head ; int n = 0 ; while ( cur != null ) { cur = cur . next ; ++ n ; } k %= n ; if ( k == 0 ) { return head ; } var fast = head ; var slow = head ; while ( k -- > 0 ) { fast = fast . next ; } while ( fast . next != null ) { fast = fast . next ; slow = slow . next ; } var ans = slow . next ; slow . next = null ; fast . next = head ; return ans ; } }
```

### Java

```java
/** * 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 ) { return head ; } ListNode cur = head ; int n = 0 ; for (; cur != null ; cur = cur . next ) { n ++; } k %= n ; if ( k == 0 ) { return head ; } ListNode fast = head ; ListNode slow = head ; while ( k -- > 0 ) { fast = fast . next ; } while ( fast . next != null ) { fast = fast . next ; slow = slow . next ; } ListNode ans = slow . next ; slow . next = null ; fast . next = head ; return ans ; } }
```

### CPP

```cpp
/** * 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 || ! head -> next ) { return head ; } ListNode * cur = head ; int n = 0 ; while ( cur ) { ++ n ; cur = cur -> next ; } k %= n ; if ( k == 0 ) { return head ; } ListNode * fast = head ; ListNode * slow = head ; while ( k -- ) { fast = fast -> next ; } while ( fast -> next ) { fast = fast -> next ; slow = slow -> next ; } ListNode * ans = slow -> next ; slow -> next = nullptr ; fast -> next = head ; return ans ; } };
```

### Python

```python
# 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 head is None or head . next is None : return head cur , n = head , 0 while cur : n += 1 cur = cur . next k %= n if k == 0 : return head fast = slow = head for _ in range ( k ): fast = fast . next while fast . next : fast , slow = fast . next , slow . next ans = slow . next slow . next = None fast . next = head return ans
```