/*
 * 演算法 / Algorithm:
 * 1) 走一遍算長度 n，並找到舊尾巴。/ Walk once to get length n and the old tail.
 * 2) k %= n 縮小旋轉量；把尾巴接回頭形成環。/ Reduce k, connect tail->head into a circle.
 * 3) 從頭走 (n - k - 1) 步到新尾巴，斷環，回傳新頭。
 *    / Walk (n - k - 1) steps to the new tail, break the circle, return new head.
 */

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

struct ListNode* rotateRight(struct ListNode* head, int k) {
    // 空串列或只有一個節點：旋轉後不變，直接回傳。
    // Empty or single-node list: rotation changes nothing, return as-is.
    if (head == NULL || head->next == NULL) return head;

    // ---- 第一趟：算長度 n，同時把 tail 停在最後一個節點 ----
    // ---- Pass 1: count length n, leave tail on the last node ----
    int n = 1;                          // 已經有 head 這一個節點 / head itself counts as 1
    struct ListNode* tail = head;       // tail 從頭開始往後走 / start walking from head
    while (tail->next != NULL) {        // 只要還有下一個節點就繼續 / while a next node exists
        tail = tail->next;              // 往後移一格 / step forward one node
        n++;                            // 長度加一 / length grows by one
    }
    // 迴圈結束後 tail 指向最後一個節點，n 是總長度。
    // After the loop, tail is the last node and n is the total length.

    // ---- 縮小 k：旋轉 n 次會回到原狀，所以只有餘數有意義 ----
    // ---- Reduce k: rotating n times is a no-op, only the remainder matters ----
    k = k % n;                          // 例如 k=2, n=5 -> k=2 / e.g. k becomes 2
    if (k == 0) return head;            // 沒有實際旋轉，直接回傳 / nothing to rotate

    // ---- 接成環：舊尾巴指回舊頭 ----
    // ---- Make it circular: old tail points back to old head ----
    tail->next = head;                  // 現在是 1->2->3->4->5->1->... / now it loops

    // ---- 找新尾巴：從頭走 (n - k - 1) 步 ----
    // ---- Find new tail: walk (n - k - 1) steps from head ----
    int stepsToNewTail = n - k - 1;     // 新尾巴是第 (n-k) 個節點(1-indexed) / the (n-k)-th node
    struct ListNode* newTail = head;    // 從頭出發 / start from head
    for (int i = 0; i < stepsToNewTail; i++) {  // 走指定步數 / take that many steps
        newTail = newTail->next;        // 每次前進一格 / advance one node each time
    }

    // ---- 斷環：新頭是新尾巴的下一個節點 ----
    // ---- Break the circle: new head is the node right after new tail ----
    struct ListNode* newHead = newTail->next;  // 記住新頭 / remember the new head
    newTail->next = NULL;               // 切斷，讓新尾巴成為真正的結尾 / cut, making it the real end

    return newHead;                     // 回傳旋轉後的頭節點 / return the rotated head
}