## Similar Problems

Similar Problems not available

# Rotate List - Leetcode Solution

## Companies:

LeetCode: Rotate List Leetcode Solution

Difficulty: Medium

Topics: linked-list two-pointers

The Rotate List problem on Leetcode asks us to rotate a linked list to the right by k places, where k is a non-negative integer.

To solve this problem, first we need to understand what it means to rotate a linked list to the right. If we have a linked list 1->2->3->4->5 and we want to rotate it to the right by 2 places, we would end up with the linked list 4->5->1->2->3.

One way to achieve this is by finding the length of the linked list and computing the index where we need to break the list. Once we know where to break the list, we can create a new tail node and point it to the original head node, and then point the new tail node's next pointer to null.

Here's the step by step approach to solving this problem:

- Compute the length of the linked list and store it in a variable.
- Compute the index where we need to break the list by calculating k % length. This is because if k is greater than length, then we would end up rotating the list by the same number of places as k % length.
- If the index is zero, the list is already in the correct position, so return the head node.
- Iterate over the linked list until we reach the node before the breaking point. Set a variable to keep track of this node.
- Set the new head node to be the node after the breaking point.
- Iterate over the linked list again starting from the new head node until we reach the end node. Set a variable to keep track of this node.
- Set the next pointer of the end node to point to the original head node.
- Set the next pointer of the node before the breaking point to null.
- Return the new head node.

Here's the Python implementation of the above algorithm:

```
def rotateRight(head, k):
# Compute the length of the linked list
length = 0
curr = head
while curr:
curr = curr.next
length += 1
# Compute the index where we need to break the list
index = k % length
# If the index is zero, return the head node
if index == 0:
return head
# Iterate over the linked list to find the node before the breaking point
curr = head
for i in range(length - index - 1):
curr = curr.next
# Set the new head node and initialize variables to track the end node and node before breaking point
new_head = curr.next
curr.next = None
end_node = new_head
while end_node.next:
end_node = end_node.next
# Set the next pointer of the end node to point to the original head node
end_node.next = head
# Return the new head node
return new_head
```

This algorithm has a time complexity of O(n), where n is the length of the linked list, and a space complexity of O(1), as we only use constant space.

## Rotate List Solution Code

`1`