Rotating a singly linked list - Leetcode Solution

Solution

If we observe carefully, we will notice two things :

• Rotating a list n times becomes brings it back to it’s original form. Therefore, even if k is larger than n, we can just rotate the list k%n times and it will still print the same output. for example if n = 5, k = 1 and n = 5 and k = 6 will end up rotating the list in the same way. So it is better to rotate the list 6%5 = 1 times instead of 6.
• Rotating the list k times can be done by just rewiring the original linked list (changing the pointers for few of the nodes), instead of actually deleting elements from the end and inserting at the front. See the below diagram for better understanding

Rewiring

Rewiring the list can be done in the following steps

• Step 1: First calculate the length of the linked list. Let it be n . Also do k = k%n . To make sure that k < n going forward. In this case, n = 5, k = 2 .
• Step 2: Find the last node at index (n - 1) and the node which will become the last node after rotation. Let us call that node before . It will be located at index n - 1 - k
• Step 3: Make the last node’s next pointer point towards the first node
• Step 4: Change the head to point to the node pointed to by before . This way we are able to change the starting node of the linked list
• Step 5: Make the before node point to NULL, since the before node will become last in the final output.

See the below images for the visualization of the whole process: