Code Implementation

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

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head or not head.next or k == 0:
            return head

        # First, compute the length and get the tail node
        length = 1
        tail = head
        while tail.next:
            tail = tail.next
            length += 1

        # Make the list circular
        tail.next = head

        # Find the new tail: (length - k % length - 1)th node
        k = k % length
        steps_to_new_tail = length - k - 1
        new_tail = head
        for _ in range(steps_to_new_tail):
            new_tail = new_tail.next

        new_head = new_tail.next
        new_tail.next = None

        return new_head
      

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head || !head->next || k == 0)
            return head;
        // Find the length and tail
        int length = 1;
        ListNode* tail = head;
        while (tail->next) {
            tail = tail->next;
            length++;
        }
        // Make it circular
        tail->next = head;
        k = k % length;
        int stepsToNewTail = length - k - 1;
        ListNode* newTail = head;
        for (int i = 0; i < stepsToNewTail; ++i) {
            newTail = newTail->next;
        }
        ListNode* newHead = newTail->next;
        newTail->next = nullptr;
        return newHead;
    }
};
      

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0)
            return head;

        // Find length and tail
        int length = 1;
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
            length++;
        }

        // Make it circular
        tail.next = head;
        k = k % length;
        int stepsToNewTail = length - k - 1;
        ListNode newTail = head;
        for (int i = 0; i < stepsToNewTail; i++) {
            newTail = newTail.next;
        }
        ListNode newHead = newTail.next;
        newTail.next = null;
        return newHead;
    }
}
      

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
    if (!head || !head.next || k === 0) return head;

    // Find the length and tail
    let length = 1;
    let tail = head;
    while (tail.next) {
        tail = tail.next;
        length++;
    }

    // Make it circular
    tail.next = head;
    k = k % length;
    let stepsToNewTail = length - k - 1;
    let newTail = head;
    for (let i = 0; i < stepsToNewTail; i++) {
        newTail = newTail.next;
    }
    let newHead = newTail.next;
    newTail.next = null;
    return newHead;
};
      

Problem Description

You are given the head of a singly linked list, head, and an integer k. Your task is to rotate the list to the right by k places. In other words, you should move the last k nodes to the front of the list, preserving their order, and adjust the rest of the list accordingly.

• All nodes must remain in the list, and no new nodes should be created or existing nodes reused.
• There is exactly one valid way to perform the rotation for any given input.
• If k is 0, or the list is empty, or has only one node, the list should remain unchanged.

For example, if the input list is 1 -> 2 -> 3 -> 4 -> 5 and k = 2, the output should be 4 -> 5 -> 1 -> 2 -> 3.

Thought Process

To solve the Rotate List problem, let's think about what rotation means for a linked list. If we rotate the list to the right by k places, the last k nodes become the first k nodes. The rest of the list follows after them.

A brute-force approach might be to move the last node to the front k times, but this would be inefficient for large lists or large values of k. Instead, we can use the properties of linked lists to find a more optimal solution:

• First, determine the length of the list. This helps because rotating by the length of the list (or any multiple) results in the same list.
• We can make the list temporarily circular, so we can easily "rotate" it by breaking it at the right spot.
• Finally, we break the circle at the correct new tail to restore the singly linked list structure.

This approach is much faster and avoids unnecessary repeated traversals.

Solution Approach

Let's break down the efficient solution step by step:

1. Compute the Length and Tail:
   • Traverse the list to find its length and the last node (tail).
   • This is necessary to handle cases where k is greater than the list length.
2. Make the List Circular:
   • Connect the tail's next pointer to the head, forming a circular linked list. This allows us to rotate the list easily.
3. Calculate the New Tail and New Head:
   • Since rotating the list by its length results in the same list, compute k % length to avoid unnecessary rotations.
   • The new tail will be at position length - k % length - 1 from the start.
   • The new head is the node after the new tail.
4. Break the Circle:
   • Set the new tail's next pointer to null (or None), restoring the singly linked list structure.
5. Return the New Head:
   • This is the rotated list.

This method ensures we only traverse the list a couple of times, making it efficient and elegant.

Example Walkthrough

Let's walk through an example for clarity:

Input: head = [1,2,3,4,5], k = 2

1. First, compute the length (5) and find the tail (node with value 5).
2. Make the list circular: 5 -> 1 (tail's next points to head).
3. Compute k % length = 2 % 5 = 2.
4. Find the new tail: position 5 - 2 - 1 = 2 (0-based index), which is the node with value 3.
5. The new head is 3.next, which is node 4.
6. Break the circle: set 3.next = null.
7. The resulting list is 4 -> 5 -> 1 -> 2 -> 3.

Time and Space Complexity

• Brute-force approach:
  • For each rotation, traverse the list to move the last node to the front. This takes O(k*n) time.
  • Space complexity is O(1) since we only rearrange pointers.
• Optimized approach (as above):
  • We traverse the list to find its length (O(n)), and again to find the new tail (O(n)), so total time is O(n).
  • Space complexity is O(1), as we only use a few pointers.

The optimized solution is much faster, especially for large lists and large values of k.

Summary

The Rotate List problem can be solved efficiently by leveraging the structure of singly linked lists. By computing the length, making the list temporarily circular, and then breaking it at the right spot, we can rotate the list in O(n) time and O(1) space. This approach avoids unnecessary repeated traversals and demonstrates the power of pointer manipulation and modular arithmetic in linked list problems.