runtime 6 ms, beats 92.60% of cpp submissions
O(n) solution with explanation

tags:

Rotate List

📖 description

給定一個 linked list 以及一個需要旋轉的次數 k，請求將 list 向右旋轉 k 次。
實際方法如下。

ex.
    Input: 
        head = [1,2,3,4,5], k = 2

    Output: 
        [4,5,1,2,3]

🧠 solution

本題只有一個需要注意的地方，就是不要真的去模擬真實的流程，可以藉由一些方法來簡化步驟。

  • 假設 list 的長度為 n ，則經過 n 次旋轉後 list 會回復原狀
  • 當有 k 次需要旋轉時，我們只需要把 n-k 位置的點當作 list 的尾巴

⏳ time complexity

遍歷兩次 list ，時間複雜度 O(n)
總時間複雜度 O(n)

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(k==0) return head;
        if(head==nullptr) return head;
        auto tmp = head;
        int cnt=1;

        // 求 list 長度
        while(tmp->next!=nullptr){
            tmp=tmp->next;
            cnt++;
        }
        tmp->next=head;
        k%=cnt;
        tmp=head;
        k=cnt-k-1; // 求結尾點
        for(int i=0;i<k;i++){
            tmp=tmp->next;
        }

        // 替換 list 開頭及結尾
        head=tmp->next;
        tmp->next=nullptr;
        return head;
    }
};