  # LeetCode - Rotate List

## Problem statement

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

Problem statement taken from: https://leetcode.com/problems/rotate-list

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

Example 2: ``````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 * 10^9
``````

### Explanation

The problem mentions rotating the list to the right. We first have to get the total number of nodes in the list. If k is greater than the list length, we first take the modulo of k by list length and then subtract the value of k from the list length. If k is smaller, we subtract the value of k from the list length.

Note: If the problem mentioned left rotation, we won't subtract k by the length of the list.

Let's check the algorithm first:

``````// empty list

- set ListNode *p = head
set listLength = 1

- loop while p->next != null
- update p = p->next
- increment listLength++

- if k > listLength
- k = k % listLength

- k = listLength - k

- if k == 0 || k == listLength

- set ListNode *current = head

- loop while k > 1 && current != null
- update current = current->next
- decrement k--

- if current == null

update current->next = null

``````

#### C++ solution

``````class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
}

int listLength = 1;

while(p->next != NULL){
p = p->next;
listLength++;
}

if(k > listLength) {
k = k % listLength;
}

k = listLength - k;

if(k == 0 || k == listLength) {
}

while(k > 1 && current != NULL){
current = current->next;
k--;
}

if(current == NULL){
}

current->next = NULL;

}
};``````

#### Golang solution

``````func rotateRight(head *ListNode, k int) *ListNode {
}

listLength := 1

for p.Next != nil {
p = p.Next
listLength++
}

if k > listLength {
k = k % listLength
}

k = listLength - k

if k == 0 || k == listLength {
}

for k > 1 && current != nil {
current = current.Next
k--
}

if current == nil {
}

current.Next = nil

}``````

#### Javascript solution

``````var rotateRight = function(head, k) {
}

let listLength = 1;

while(p.next != null) {
p = p.next;
listLength++;
}

if(k > listLength) {
k = k % listLength;
}

k = listLength - k;

if(k == 0 || k == listLength){
}

while(k > 1 && current != null) {
current = current.next;
k--;
}

if(current == null){
}

current.next = null;

};``````

#### Dry Run

Let's dry-run our algorithm to see how the solution works.

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

false

Step 2: ListNode *p = head
int listLength = 1

Step 3: loop while p->next != nil
p = p->next
listLength++

The above loop reaches at the last node of the linked list.

listLength = 5

|            |
[1, 2, 3, 4, 5]

Step 4: if k > listLength
2 > 5
false

Step 5: k = listLength - k
= 5 - 2
= 3

Step 6: if k == 0 || k == listLength
3 == 0 || 3 == 5
false

Step 7: ListNode *current = head

|           |
current - [1, 2, 3, 4, 5]

Step 8: loop while k > 1 && current != NULL
3 > 1 && current != NULL
true

current = current->next

|           |
[1, 2, 3, 4, 5]
|
current

k--
k = 2

2 > 1 && current != NULL
true

current = current->next

|           |
[1, 2, 3, 4, 5]
|
current

k--
k = 1

1 > 1 && current != NULL
false

Step 9: if current == NULL
false

|
p - [5, 1, 2, 3, 4]
|
current

|
p - [5, 1, 2, 3, 4]
|
current

current->next = NULL