Algorithm

When asked to rotate a linked list to the right k times, we are essentially moving the last node to the front of the list, k times. Each rotation means: take the last node, disconnect it from the list, insert it at the front (head) of the list. We repeat this process k times. This approach is straightforward but not efficient because each rotation requires a traversal to the second-last node, which takes linear time. So in total, if we rotate k times and for each rotation we traverse the list (of n nodes), hence this approach is inefficient for large inputs.

If the linked list is empty or has only one node, or k is 0, return the head as-is.
Repeat the following steps k times:
- Initialize a pointer to traverse the list from head.
- Traverse to the second-last node of the list.
- Store the last node separately.
- Make the second-last node point to null (removing the last node).
- Insert the stored last node at the beginning by:
  - Pointing its next to the current head.
  - Updating the head to this node.
Return the new head of the list.

Code

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758