Last Updated: 2 Dec, 2020

Rotate Linked List

Moderate

Asked in companies

Solve now

Problem statement

You are given a linked list having ‘n’ nodes and an integer ‘k’.

You have to rotate the linked list to the right by ‘k’ positions .

Example :

Input: linked list = [1 2 3 4] , k = 2

Output: 3 4 1 2

Explanation:
We have to rotate the given linked list to the right 2 times. After rotating it to the right once it becomes 4->1->2->3. After rotating it to the right again, it becomes 3->4->1->2.

Input Format :

The first line of the input contains a single integer 'n', denoting the number of nodes in the linked list.

The next line contains 'n' space-separated integers, denoting the elements of the linked list.

The next line contains an integer ‘k’, representing the number of positions up to the given linked list that has to rotate.

Output Format :

Return the head of the linked list after rotating it.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function. Elements of your returned linked list will be printed in a single line.

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

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’

Solve now