Rotate Linked List

Posted: 2 Dec, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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:
 

  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.
Try Problem