LeetCode Problem: Rotate List – Efficient Solution Explained

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:

1. Handle edge cases: If the head of the list is null or k is 0, we return the list as it is.
2. 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.
3. Determine the effective rotations: Use the modulo operation (k % size) to avoid unnecessary rotations when k is larger than the list size.
4. 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.
5. Re-arrange the pointers: Disconnect the circular list to form the rotated list.

Solution Code:

javaCopy codeclass 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:

1. 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.
2. 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.
3. 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.
4. 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.