題目網址：https://leetcode.cn/problems/rotate-list/

題意：給一 linked list 的 head 和一整數 k, 將 linked list 每個 node 向右移 k 個位置。

Solution：

想法：將 linked list 分成兩個部分, 倒數 k 個 node(藍色部分)、剩餘部分(綠色部分)

  • 先將 tail->next 設為藍色部分的 head, 並把綠色部分的 tail->next 指向 null
  • 再將藍色部分的 tail 指向綠色部分的 head, 並把藍色部分的 head 設為 newHead

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (k == 0 || !head) {
            return head;
        }

        int len = 1;
        ListNode *tail = head;

        // 得到 len & 藍色部分的 tail
        while (tail->next) {
            ++len;
            tail = tail->next;
        }

        // 因為 k 有可能會大於 len(如 example 2), 所以要 k % len(循環)
        k %= len; // 藍色部分的長度
        if (k == 0) {
            return head;
        }

        ListNode *cur = head;
        // cur 為綠色部分的 tail
        for (int i = 0; i < len - k - 1; ++i) {
            cur = cur->next
        }

        ListNode *newHead = cur->next; // 藍色部分的 head
        cur->next = nullptr; // 綠色部分的 tail 指向 null
        tail->next = head; // 藍色部分的 tail 指向綠色部分的 head

        return newHead;
    }
};
  • time：$O(n)$ ➔ 遍歷整個 linked list
  • space：$O(1)$ ➔ 只需常數空間