61. Rotate List

/**
 * Problem: LeetCode 61 - Rotate List
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
/**
 * 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; }
 * }
 */
/**
 * Problem: LeetCode 61 - Rotate List
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }

        // Step 1: Find the length and tail of the linked list
        int len = 1;
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
            len++;
        }

        // Step 2: Normalize k
        k = k % len;
        if (k == 0) {
            return head;
        }

        // Step 3: Connect tail to head to form a circular list
        tail.next = head;

        // Step 4: Find the new tail at (len - k) steps from tail
        int stepsToNewTail = len - k;
        ListNode newTail = tail;
        for (int i = 0; i < stepsToNewTail; i++) {
            newTail = newTail.next;
        }

        // Step 5: Disconnect and set new head
        ListNode newHead = newTail.next;
        newTail.next = null;

        return newHead;
    }
}

"""
Problem: LeetCode 61 - Rotate List
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
from typing import Optional

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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

        # Step 1: Find length and tail
        length = 1
        tail = head
        while tail.next:
            tail = tail.next
            length += 1

        # Step 2: Normalize k
        k %= length
        if k == 0:
            return head

        # Step 3: Make it circular
        tail.next = head

        # Step 4: Find new tail (length - k steps from tail)
        steps_to_new_tail = length - k
        new_tail = tail
        for _ in range(steps_to_new_tail):
            new_tail = new_tail.next

        # Step 5: Disconnect and return new head
        new_head = new_tail.next
        new_tail.next = None

        return new_head

/**
 * Problem: LeetCode 61 - Rotate List
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
/**
 * 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) {}
 * };
 */
/**
 * Problem: LeetCode 61 - Rotate List
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head || !head->next || k == 0) {
            return head;
        }

        // Step 1: Find length and tail
        int len = 1;
        ListNode* tail = head;
        while (tail->next != nullptr) {
            tail = tail->next;
            len++;
        }

        // Step 2: Normalize k
        k = k % len;
        if (k == 0) {
            return head;
        }

        // Step 3: Form circular list
        tail->next = head;

        // Step 4: Find new tail
        int stepsToNewTail = len - k;
        ListNode* newTail = tail;
        for (int i = 0; i < stepsToNewTail; i++) {
            newTail = newTail->next;
        }

        // Step 5: Disconnect circular list
        ListNode* newHead = newTail->next;
        newTail->next = nullptr;

        return newHead;
    }
};

/**
 * Problem: LeetCode 61 - Rotate List
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * Problem: LeetCode 61 - Rotate List
 * Difficulty: Medium
 * Language: JavaScript (ES6+ / Node.js)
 * Author: CodeByTushu
 *
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
    if (!head || !head.next || k === 0) {
        return head;
    }

    // Step 1: Find length and tail
    let len = 1;
    let tail = head;
    while (tail.next !== null) {
        tail = tail.next;
        len++;
    }

    // Step 2: Normalize k
    k = k % len;
    if (k === 0) {
        return head;
    }

    // Step 3: Form circular list
    tail.next = head;

    // Step 4: Find new tail
    const stepsToNewTail = len - k;
    let newTail = tail;
    for (let i = 0; i < stepsToNewTail; i++) {
        newTail = newTail.next;
    }

    // Step 5: Disconnect circular list
    const newHead = newTail.next;
    newTail.next = null;

    return newHead;
};