25. K 個一組翻轉鏈表

思路

假設 $k=3$，鏈表內容是 $\begin{bmatrix} \text{\blue{a, b, c,} \red{d, e, f}, g, h} \end{bmatrix}$，
每三個一組翻轉，假如不夠就保持原樣。更改後的矩陣為 $\begin{bmatrix} \text{\blue{c, b, a,} \red{f, e, d,} g, h} \end{bmatrix}$。

• teamEnd(ListNode* head, int k)：找到這一組的尾端節點。
  • --k是因為 k 個節點之間只有k - 1條線。
• rev(ListNode* head, ListNode* tail)：將head到tail節點反轉。

程式碼

鏈表

class Solution {
private:
    ListNode* teamEnd(ListNode* head, int k) {
        --k;
        while(head != nullptr && k > 0) {
            head = head -> next;
            --k;
        }
        return head;
    }
    void rev(ListNode* head, ListNode* tail) { 
        // 不需要管 nullptr 的情況，因為呼叫時不可能會是 nullptr。
        ListNode *prev = nullptr, *curr = head, *next = nullptr;
        while(curr != tail -> next) {
            next = curr -> next;
            curr -> next = prev;
            prev = curr;
            curr = next;
        }
        // head <- ... <- tail, head -> (tail -> next)
        head -> next = tail -> next; // 連到尾端的下一個
    }
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // 第一組
        ListNode* start = head; 
        ListNode* tail = teamEnd(start, k);
        if(tail == nullptr) return head;
        head = tail; // 回傳的頭節點需要變動
        rev(start, tail);

        ListNode* lastTeamEnd = start; // 第一組反轉前起點
        while(lastTeamEnd != nullptr) {
            start = lastTeamEnd -> next; // 下一組的開頭
            tail = teamEnd(start, k);
            if(tail == nullptr) return head;
            rev(start, tail);
            lastTeamEnd -> next = tail;
            lastTeamEnd = start;
        }
        return head;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$