runtime 8 ms, beats 99.56% of cpp submissions
O(n) solution with explanation

tags: linked list, pointer

Reverse Nodes in k-Group

📖 description

給定一個 linked list 與數字 k ，將 list 內的元素每 k 個一組進行反轉，要求 in place 的完成，也就是不可以使用額外的儲存空間。

ex.
    1 -> 2 -> 3 -> 4 -> 5  (k=2)

    2 -> 1 -> 4 -> 3 -> 5

    最後的 5 因為沒辦法組成一群所以不用反轉

🧠 solution

如果不要求 in place 的話可以很簡單的用陣列儲存，然後分群做反轉了，這是因為陣列可以 random access 每個元素，但使用 list 就沒辦法往回走。

反轉的部分從每個點的數值變成點間的連結，會比較方便操作，在這裡有一些需要注意的點，比如反轉某個群組之後，要維護新的開頭，以及遇到結尾時不要反轉。

⏳ time complexity

獲得 list 長度需要 O(n) ，反轉 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
28
29
30
31
32
33
34
35
class Solution {
public:
    int get_len(ListNode* l){   // 獲得 list 長度
        int cnt = 0;
        while(l!=nullptr){
            l = l->next;
            cnt++;
        }
        return cnt;
    }
    ListNode* reverse(ListNode* head,int k,int g){    // 對 head 後方的 k 個元素反轉
        if(g==0){               // 如果已經沒有群組了
            return head;
        }
        g--;                    // 到下一個群組
        ListNode* now=head;
        ListNode* slow=nullptr;
        ListNode* fast=nullptr;
        for(int i=0;i<k;i++){   // 把 k 個元素之間的連接反轉
            fast=now->next;
            now->next=slow;
            slow=now;
            now=fast;
        }
        head->next=reverse(fast,k,g);   // 反轉下一個群組
        return slow;                    // 回傳該群組新的開頭
    }
    ListNode* reverseKGroup(ListNode* head, int k){
        int count=0;
        ListNode* tmp=head;
        int s = get_len(tmp);
        s/=k;
        return reverse(head,k,s);
    }
};