# Rotate Linked List

Posted: 2 Dec, 2020

Difficulty: Moderate

#### You have been given a Linked List having ‘N’ nodes and an integer ‘K’. You have to rotate the Linked List by ‘K’ positions in a clockwise direction.

#### Example :

```
Given Linked List : 1 2 3 4 -1 and K : 2
Then the modified Linked List after K rotation : 3 4 1 2
```

##### Input Format :

```
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case contains single space-separated integers, denoting the elements of the Linked List with -1 being the last element denoting the end of the List (or null element).
The next line of each test case contains an integer ‘K’, representing the number of positions up to the given Linked List that has to rotate.
```

##### Output Format :

```
For each test case, print the elements of the resultant Linked List after rotating by ‘K’ positions in a clockwise direction.
```

##### Note:

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

##### Constraints :

```
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^5
0 <= node.data <= 10^9 and node.data != -1
0 <= ‘K’ <= 10^5
Time Limit: 1 sec
```

Approach 1

Find the length of the Linked List to check whether the ‘K’ is greater than the Length of the Linked List or not. Take a modulo of ‘K’ with its length if it is greater than the length. Reach the (‘K’+1)th node from last and change the pointers of nodes to get a rotated Linked List.

Here is the algorithm:

- Base Condition : If ‘HEAD’ is equal to ‘NULL’ or ‘K’ is equal to 0, then return ‘HEAD’ of the Linked List.
- Create a variable (say, ‘LEN’) which will store the length of the linked list and initialise it to 1.
- Create a temporary node (say, ‘TEMP’) which will be used to find the length of the Linked List and initialise it as ‘HEAD’.
- Run a loop while ‘TEMP’.next is not equal to ‘NULL’:
- Update ‘TEMP’ as ‘TEMP’.next and increment the ‘LEN’ by 1.

- If ‘LEN’ is less than ‘K’, then update ‘K’ as ‘K’ % ‘LEN’ ( To make ‘K’ come in range of 0 to ‘LEN’).
- Update ‘K’ as ‘LEN’ - ‘K’ (To reach (‘K’+1)th node from end).
- If ‘K’ is equal to ‘LEN’, then:
- Return ‘HEAD’ (Number of rotations are the same as length which will not change the original list).

- Create a variable (say, ‘COUNT’) which will be used to reach (‘K’ + 1)th node from end and initialise it to 1.
- Create a node (say, ‘CURRENT’) which will store the current node of Linked List and initialise it as ‘HEAD’.
- Run a loop while ‘COUNT’ is less than ‘K’ and ‘CURRENT’ is not equal to ‘NULL’:
- Update ‘CURRENT’ as ‘CURRENT’.next and Increment ‘COUNT’ by 1.

- If ‘CURRENT’ is equal to ‘NULL’., then return ‘HEAD’ of the Linked List.
- Update ‘TEMP’.next as ‘HEAD’ (Make the last pointer connect to ‘HRAD’).
- Update ‘HEAD’ as ‘CURRENT’.next (Make Kth node from last the new ‘HEAD’).
- Update ‘CURRENT’.next as ‘NULL’ (Make (‘LEN’ - ‘K’)th point to ‘NULL’).
- Finally, return the ‘HEAD’ of the Linked List.

Approach 2

The basic idea of this approach is to first convert a linked list to circular linked list by making the last pointer point to head. Change the pointers of (K+1)th node to get a rotated linked list.

The steps are as follows :

- Base Condition : if ‘HEAD’ is equal to ‘NULL’ or ‘K’ is equal to 0, then return ‘HEAD’ of the linked list.
- Create a variable (say, ‘LEN’) which will store the length of the linked list and initialise it to 1.
- Create a temporary node (say, ‘TEMP’) which will be used to find the length of the Linked List and initialise it with ‘HEAD’.
- Run a loop while ‘TEMP’.next is not equal to ‘NULL’.
- Update ‘TEMP’ as ‘TEMP’.next and increment the ‘LEN’ by 1.

- If ‘LEN’ is less than ‘K’, then update ‘K’ as ‘K’ % ‘LEN’ ( To make ‘K’ come in range of 0 to ‘LEN’).
- If ‘K’ is equal to ‘LEN’, then:
- return ‘HEAD’ (Number of rotations are the same as length which will not change the original list).

- Update ‘TEMP'.next as ‘HEAD’. (To make a circular linked list)
- Re - initialise ‘TEMP’ as ‘HEAD’.
- Run a loop for ‘i’ = 0 to ‘abs(LEN - K - 1)’ : (To reach (K+1)th node from end).
- Update ‘TEMP’ as ‘TEMP’.next

- Update ‘HEAD’ as ‘TEMP’.next. (Make Kth node from the last new ‘HEAD’)
- Update ‘TEMP’.next as ‘NULL’. (Make (K + 1)th node point to ‘NULL’).
- Finally, return ‘HEAD’

SIMILAR PROBLEMS

# Replace The Linked List

Posted: 1 Apr, 2021

Difficulty: Moderate

# Implement a Queue

Posted: 27 Jul, 2021

Difficulty: Easy

# Vertical Sum in BST

Posted: 27 Jul, 2021

Difficulty: Moderate

# Remove Duplicates From Sorted List

Posted: 21 Sep, 2021

Difficulty: Easy

# Binary Linked List To Integer

Posted: 22 Sep, 2021

Difficulty: Easy