Rotate Linked List

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
116 upvotes
Asked in companies
Morgan StanleyPharmEasyGeeksforGeeks

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.


Detailed explanation ( Input/output format, Notes, Images )
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.


Sample Input 1 :
6
1 2 3 4 5 6
2


Sample Output 1 :
5 6 1 2 3 4


Explanation For Sample Input 1 :
For the first test case, after 1st clockwise rotation the modified linked list will be : 6->1->2->3->4->5
After, 2nd clockwise rotated the modified linked list will be : 5->6->1->2->3->4.
Thus the output is: 5 6 1 2 3 4.


Sample Input 2 :
3
3 6 9 
0


Sample Output 2:
3 6 9


Explanation For Sample Input 2 :
In this test case, ‘k’ is 0 therefore there will be no rotation, so the linked list remains unchanged.


Expected Time Complexity:
Try to do this in O(n).


Constraints :
1 <= n <= 10^5
0 <= Node.data <= 10^9 
0 <= k <= 10^5

Time Limit: 1 sec


Hint

Do the changes at (K+1)th node from last.

Approaches (2)
Brute Force

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:
 

  1. Base Condition : If ‘HEAD’ is equal to ‘NULL’ or ‘K’ is equal to 0, then return ‘HEAD’ of the Linked List.
  2. Create a variable (say, ‘LEN’) which will store the length of the linked list and initialise it to 1.
  3. Create a temporary node (say, ‘TEMP’) which will be used to find the length of the Linked List and initialise it as ‘HEAD’.
  4. Run a loop while ‘TEMP’.next is not equal to ‘NULL’:
    • Update ‘TEMP’ as ‘TEMP’.next and increment the ‘LEN’ by 1.
  5. If ‘LEN’ is less than ‘K’, then update ‘K’ as ‘K’ % ‘LEN’ ( To make ‘K’ come in range of 0 to ‘LEN’).
  6. Update ‘K’ as ‘LEN’ - ‘K’ (To reach (‘K’+1)th node from end).
  7. If ‘K’ is equal to ‘LEN’, then:
    • Return ‘HEAD’ (Number of rotations are the same as length which will not change the original list).
  8. Create a variable (say, ‘COUNT’) which will be used to reach (‘K’ + 1)th node from end and initialise it to 1.
  9. Create a node (say, ‘CURRENT’) which will store the current node of Linked List and initialise it as ‘HEAD’.
  10. 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.
  11. If ‘CURRENT’ is equal to ‘NULL’., then return ‘HEAD’ of the Linked List.
  12. Update ‘TEMP’.next as ‘HEAD’  (Make the last pointer connect to ‘HRAD’).
  13. Update ‘HEAD’ as ‘CURRENT’.next (Make Kth node from last the new ‘HEAD’).
  14. Update ‘CURRENT’.next as ‘NULL’  (Make (‘LEN’ - ‘K’)th point to ‘NULL’).
  15. Finally, return the ‘HEAD’ of the Linked List.
Time Complexity

O(N), where ‘N’ is the size of the Linked List.

 

Since we are traversing all nodes of the Linked List to find the length and after that we are rotating the first ‘K’ nodes of the Linked List. Hence, the overall time complexity will be O(N).

Space Complexity

O(1)

 

Since we are not using any extra space, therefore space complexity will be O(1).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Rotate Linked List
Full screen
Console