C++で連結リストをk個ずつ反転するアルゴリズムの解説

連結リストが与えられたとき、k個ずつのグループに分けてノードを反転し、変更後のリストを返すことを考えます。ここでkは正の整数であり、連結リストの長さ以下であるものとします。また、ノード数がkの倍数でない場合、末尾に余ったノードは元の順序のまま維持します。

例えば、連結リストが [1,2,3,4,5,6,7] で k = 3 の場合、出力は [3,2,1,6,5,4,7] となります。最初の3ノード（1,2,3）が「3,2,1」に、次の3ノード（4,5,6）が「6,5,4」に反転され、残りの7はそのままの位置に留まります。

アルゴリズムの考え方

この問題は、再帰を利用した以下の手順で解くことができます。

• solve() というメソッドを定義します。引数として連結リストの先頭（head）、パーティション数（partCount）、および k を受け取ります。
• partCount が 0 の場合は、head をそのまま返します。
• newHead := head、prev := null、x := k として初期化します。
• newHead が null ではなく、かつ x が 0 になるまで以下を繰り返します。
  • temp := newHead の次のノード、newHead の next := prev とします。
  • prev := newHead、newHead := temp と更新します。
• head の next := solve(newHead, partCount − 1, k) とし、次のグループを再帰的に処理します。
• prev（反転後のグループの先頭）を返します。
• メインメソッドからは、solve(head, リストの長さ ÷ k, k) を呼び出して結果を取得します。

C++での実装例

それでは、実際の実装を見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
void print_vector(vector<vector<auto>> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << "[";
        for(int j = 0; j <v[i].size(); j++){
            cout << v[i][j] << ", ";
        }
        cout << "],";
    }
    cout << "]"<<endl;
}
class ListNode{
    public:
        int val;
        ListNode *next;
        ListNode(int data){
            val = data;
            next = NULL;
        }
};
ListNode *make_list(vector<int> v){
    ListNode *head = new ListNode(v[0]);
    for(int i = 1; i<v.size(); i++){
        ListNode *ptr = head;
        while(ptr->next != NULL){
            ptr = ptr->next;
        }
        ptr->next = new ListNode(v[i]);
    }
    return head;
}
void print_list(ListNode *head){
    ListNode *ptr = head;
    cout << "[";
    while(ptr){
        cout << ptr->val << ", ";
        ptr = ptr->next;
    }
    cout << "]" << endl;
}
class Solution {
public:
    ListNode* solve(ListNode* head, int partitionCount, int k){
        if(partitionCount == 0)return head;
        ListNode *newHead = head;
        ListNode* prev = NULL;
        ListNode* temp;
        int x = k;
        while(newHead && x--){
            temp = newHead->next;
            newHead->next = prev;
            prev = newHead;
            newHead = temp;
        }
        head->next = solve(newHead, partitionCount - 1, k);
        return prev;
    }
    int calcLength(ListNode* head){
        int len = 0;
        ListNode* curr = head;
        while(curr){
            len++;
            curr = curr->next;
        }
        return len;
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        int length = calcLength(head);
        return solve(head, length / k, k);
    }
};
main(){
    vector<int> v = {1,2,3,4,5,6,7};
    ListNode *head = make_list(v);
    Solution ob;
    print_list(ob.reverseKGroup(head, 3));
}

入力

1,2,3,4,5,6,7
3

出力

[3, 2, 1, 6, 5, 4, 7]

処理のポイント

この実装では、まず calcLength() でリスト全体の長さを計算し、完全なグループの数（length ÷ k）を求めています。solve() 関数は各呼び出しごとに1つのグループを反転し、残りの部分に対して自分自身を再帰的に呼び出すことで、リスト全体を効率的に処理します。時間計算量は O(n)、空間計算量は再帰の深さに応じて O(n/k) となります。