Technical Interview Question: Rotate List

You are given a singly linked list and an integer k. Rotate the linked list to the right by k places.

Example:

Input: 1->2->3->4->5->NULL, k = 2

Output: 4->5->1->2->3->NULL

Note:

• k is a non-negative integer and it does not exceed the length of the list.

Requirements:

• You must modify the original list, do not create a new list.

Answer

To solve this problem, we will use the following approach:

1. Traverse the list to find the length and the tail of the list.
2. Connect the tail of the list to the head to form a cycle.
3. Find the new head and tail of the list after rotation and disconnect the cycle.

Here's the step-by-step detailed explanation:

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def rotateList(head, k):
    if not head or k == 0:
        return head

    # Step 1: Traverse the list to find the length and the tail of the list
    length = 1
    current = head
    while current.next:
        current = current.next
        length += 1
    tail = current
    
    # Step 2: Connect the tail of the list to the head to form a cycle
    tail.next = head
    
    # Step 3: Find the new head and tail of the list after rotation and disconnect the cycle
    k %= length  # Adjust k if it exceeds the length of the list
    new_head_index = length - k
    current = head
    for _ in range(new_head_index - 1):
        current = current.next
    new_head = current.next
    current.next = None  # Disconnect the cycle
    
    return new_head

This approach allows us to efficiently rotate the linked list to the right in O(n) time complexity, where n is the length of the list, and O(1) space complexity.