Rotate a Linked List

In this article, we will solve the problem of rotating a linked list to the right by a given K places.

Example: 

1 -> 2 -> 3 -> 4 -> 5 -> NULL

If k=2,

Output;

4 -> 5 -> 1 -> 2 -> 3 -> NULL

Solution:

To rotate the linked list to the right by k places, we will go with the following approach:

1.    Calculate the Length:

o   Traverse the linked list to find its length and determine the rotation value by taking k mod  length of the list.

2.    Find the Break Point:

o   Traverse the list again to find the node n that will become the new head after rotation.

3.    Perform Rotation:

o   Adjust the pointers to rotate the list, making the node n the new head.

Time Complexity: O(N)

Space Complexity: O(1)