Rotation of Linked List

We will see the logic to rotate a singly linked list by k nodes. Rotation of linked list can be done in two ways: Clockwise rotation and Anti-clockwise rotation.In this post, we will discuss the clockwise rotation of linked list by k nodes.

In clockwise rotation, remove the root node from start of the linked list and add it to the end of the linked list.

Example:

10 -> 7 -> 76 -> 19 -> 9 -> 57 – >Null

7 -> 76 -> 19 -> 9 -> 57 – > 10 – >Null  (After first rotation)

76 -> 19 -> 9 -> 57 – > 10 – > 7 – >Null (After second rotation)

19 -> 9 -> 57 – > 10 – > 7 – > 76 ->Null (After third rotation)

 

While rotating the linked list, we should keep in mind that API should not create any new object as well as not delete the existing object.Rotation process will just rearrange the links of the nodes. We will write the API which will accept the Integer positive value as number of rotations k and API will rotate the linked list by k nodes.

Logically, if we rotate the linked list N times where N=size of linked list , we will get the original linked list.Suppose, size of a linked list is 5 and number of rotation is 22, so ideally we should not rotate the linked list 22 times. 22 times rotation will be equivalent to 2 times rotation because after 20th rotation, we will have original linked list.
See the below algorithm and execution process.[Try Yourself]

Algorithm:

  1. Calculate effective Rotation. effectiveRotation = (numberOfRatation) % (size of linked list) . “%” in JAVA will give the remainder.
  2. Write a For Loop for effective rotation . for (int i=0 ; i < effectiveRotation ; i++)
  3. Each loop will be responsible to rotate the linked list by 1 node. Follow the below steps for each loop.
  4. Declare currentNode =root node.
  5. update rootNode = currentNode.next.
  6. Nullify the next node of currentNode.
  7. Get the last node of the linked list.
  8. Set the next node of lastNode as currentNode.

Execution Process:

 

See the below rotate method where input argument is positive integer value and method will rotate the linked list.

Output:

*****************************************************************************************

Original List: [10,7,76,19,9,57]

Linked List after 3 rotations: [19,9,57,10,7,76]

Linked List after 21 rotations: [10,7,76,19,9,57]
*****************************************************************************************

In the above main method, first we are rotating the linked list by 3 nodes. In second rotate method call we are rotating 21 times which is equivalent to 3 times ( 21 % 6[size of linked list]). Finally, the linked list will rotate totally 6 times and result will be same as original list.

We saw the clockwise rotation of linked list. For anti-clockwise rotation, we should remove the last node and add it to the root of the linked list. Try yourself. If finding any difficulty, please post a comment. Happy to hear you 🙂

Hope you like this post. Please leave your comments/suggestions.

 

You may like –

 

Top