Rotate List - Leetcode Solution

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:

1. Compute the length of the linked list and store it in a variable.
2. 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.
3. If the index is zero, the list is already in the correct position, so return the head node.
4. Iterate over the linked list until we reach the node before the breaking point. Set a variable to keep track of this node.
5. Set the new head node to be the node after the breaking point.
6. 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.
7. Set the next pointer of the end node to point to the original head node.
8. Set the next pointer of the node before the breaking point to null.
9. 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.

1