LeetCode 61. Rotate List [Medium] [C++] 解題筆記

這題給定一個 Linked-list 要求從移動最尾端的 node 到最前端 一共 K 次。

EX:

       1->2->3->4->5->NULL ,  k = 2

rotate 1 steps: 5->1->2->3->4->NULL
rotate 2 steps: 4->5->1->2->3->NULL

想法:

        這題需要注意的是 k 值有可能比 list 長度還大，因此我們需要先遍歷一次 list 得到長度，

之後再將 k % list長度 得到實際需要rotate的次數(因為rotate list長度次等於回到一開始的狀態)，

之後將最後一個 node 指向 head，然後從頭走 len - k 個 node 就是新的head的前一個node(新的tail)，

把它下一個node當成新的 head 然後把它指向 NULL，收工！

 < len - k 個 > < k 個 >      新 head 為從頭走 len - k 個node

  1 -> 2 -> 3 -> 4 -> 5        新 tail 為從尾端走 len - k 個node

* Linked-list 題也需要特別注意 edge case，ex: 空的 list, 只有一個node的list...

Time Complexity: O(n) time, O(1) space

完整程式碼:

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == nullptr || head->next == nullptr) { return head; }
        ListNode* cur = head;
        int len = 1;
        while (cur->next != nullptr) {
            cur = cur->next;
            len++;
        }
        k = k % len;
        // k == 0 means not need to rotate, since it will same as not rotate
        if (k == 0) { return head; }
        // cur is tail currently
        cur->next = head;
        // find new tail
        for (int i = 0; i < len - k; i++) {
            cur = cur->next;
        }
        // new head is next node of new tail
        head = cur->next;
        cur->next = NULL;
        
        return head;
    }
};