/*
 * 演算法 / Algorithm (與 C 版相同 / same as the C version):
 * 走一遍算長度並找尾巴 -> k %= n -> 接成環 -> 走 (n-k-1) 步找新尾巴 -> 斷環回傳新頭。
 * Count length + find tail -> reduce k -> circularize -> walk (n-k-1) steps -> break, return new head.
 */

// LeetCode 提供的節點定義 / Node definition provided by LeetCode:
// struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} };

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        // 空串列或單一節點：旋轉不改變任何東西。
        // Empty or single node: rotation is a no-op.
        if (head == nullptr || head->next == nullptr) return head;

        // ---- 第一趟：算長度 n，tail 停在最後一個節點 ----
        // ---- Pass 1: compute length n; tail ends on the last node ----
        int n = 1;                       // head 本身算一個 / head counts as one
        ListNode* tail = head;           // 從頭開始走 / start at head
        while (tail->next != nullptr) {  // 還有下一個就繼續 / while a next node exists
            tail = tail->next;           // 前進一格 / move forward
            ++n;                         // 長度加一 / increase length
        }

        // ---- 縮小 k：只有 k % n 有意義 ----
        // ---- Reduce k: only k % n matters ----
        k %= n;                          // 等同 k = k % n / same as k = k % n
        if (k == 0) return head;         // 沒有實際旋轉 / no real rotation needed

        // ---- 接成環 ----
        // ---- Make it circular ----
        tail->next = head;               // 尾巴接回頭 / last node loops back to head

        // ---- 走 (n - k - 1) 步找新尾巴 ----
        // ---- Walk (n - k - 1) steps to reach the new tail ----
        ListNode* newTail = head;        // 從頭出發 / start from head
        for (int i = 0; i < n - k - 1; ++i) {  // 走固定步數 / take fixed number of steps
            newTail = newTail->next;     // 每次前進一格 / advance one node
        }

        // ---- 斷環，取得新頭 ----
        // ---- Break the circle, get the new head ----
        ListNode* newHead = newTail->next;  // 新尾巴的下一個就是新頭 / node after new tail is the new head
        newTail->next = nullptr;         // 切斷環，成為真正結尾 / cut the loop to make a proper end

        return newHead;                  // 回傳新頭 / return the rotated head
    }
};