In this post, we’ll discuss how to solve the LeetCode problem “Rotate List,” which involves rotating a singly-linked list by a given number of positions, `k`

. Below, I’ll break down the approach step by step to help you understand how to achieve an optimal solution.

## Problem Description:

You are given the head of a linked list, and you need to rotate it to the right by `k`

places. This is a typical problem that can be solved with efficient techniques to handle cases where `k`

is larger than the length of the list.

#### Example:

Given a linked list:`1 -> 2 -> 3 -> 4 -> 5`

,

If `k = 2`

, the output should be:`4 -> 5 -> 1 -> 2 -> 3`

.

If `k = 5`

(the size of the list), the list remains the same.

## Key Insights:

**Rotation by k greater than list size**: When`k`

exceeds the length of the list, rotating the list by`k`

places is the same as rotating by`k % size`

. For example, rotating by 13 places in a 5-node list is equivalent to rotating by`13 % 5 = 3`

places.**Breaking and reconnecting the list**: To achieve the rotation, we first create a circular linked list by connecting the last node to the first. After that, we break the link at the correct position to form the rotated list.

## Approach:

**Handle edge cases**: If the head of the list is`null`

or`k`

is`0`

, we return the list as it is.**Find the size of the linked list**: Traverse the list to determine its size and locate the last node to connect it to the head, forming a circular list.**Determine the effective rotations**: Use the modulo operation (`k % size`

) to avoid unnecessary rotations when`k`

is larger than the list size.**Locate the new head**: Traverse the list to the node where the rotation should break the list into two parts: the first part will become the tail, and the second part will become the head.**Re-arrange the pointers**: Disconnect the circular list to form the rotated list.

## Solution Code:

`javaCopy code````
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head == null || k == 0) {
return head;
}
int size = 1;
ListNode curr = head;
// Find the size of the list and the last node
while(curr.next != null) {
size++;
curr = curr.next;
}
// Make the list circular by connecting the last node to the head
curr.next = head;
// Calculate the number of rotations we actually need
int noOfRotation = k % size;
// Locate the new tail of the rotated list
ListNode tail = head;
for(int i = 1; i < size - noOfRotation; i++) {
tail = tail.next;
}
// The node after tail becomes the new head
ListNode newHead = tail.next;
// Break the circular link
tail.next = null;
return newHead;
}
}
```

## Explanation:

**Base Case**: We first handle the case where the list is empty or`k`

is`0`

. In these cases, no rotation is required, so we simply return the head.**Finding the Size**: We traverse the list to count the number of nodes (`size`

) and to get a reference to the last node, which is necessary for creating a circular linked list.**Modulo Operation**: Since rotating by the size of the list results in the same list, we use the modulo operation to reduce the number of unnecessary rotations.**Breaking the Loop**: After determining the new head and tail, we break the circular linked list to restore it to a linear structure, forming the rotated list.

## Complexity:

**Time complexity**: O(n), where`n`

is the number of nodes in the linked list. We traverse the list twice—once to find the size and once to locate the new head.**Space complexity**: O(1), as we are only using a few extra variables.

## Conclusion:

This approach efficiently solves the problem while handling both small and large values of `k`

. If you’re interested in a more detailed explanation or want to see the solution in action, feel free to check out my YouTube video explaining the problem and solution.