C++で指定したサイズのグループごとに双方向連結リストを反転する方法

問題概要

この問題では、双方向連結リストの先頭ノードへのポインタと整数 k が与えられます。リストをサイズ k のグループごとに区切り、各グループ内でノードの並びを反転する必要があります。

たとえば、次のようになります。

入力：1 <-> 2 <-> 3 <-> 4 <-> 5（双方向連結リスト）、k = 3
出力：3 <-> 2 <-> 1 <-> 5 <-> 4

解法のアプローチ

この問題は再帰を用いたアルゴリズムで効率的に解くことができます。基本的な考え方は以下の通りです。

• 先頭から k 個のノードを取り出し、prev と next のポインタを入れ替えながら反転する。
• k 個反転したら、残りのリストに対して同じ関数を再帰的に呼び出す。
• 反転後のグループの末尾（元の先頭ノード）の next を、再帰呼び出しの戻り値につなぐことで、グループ同士を正しく連結する。

C++での実装例

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node *next, *prev;
};

// ノードをリストに追加する push 関数
Node* push(Node* head, int data) {
    Node* new_node = new Node();
    new_node->data = data;
    new_node->next = NULL;
    Node* TMP = head;
    if (head == NULL) {
        new_node->prev = NULL;
        head = new_node;
        return head;
    }
    while (TMP->next != NULL) { // 末尾ノードまで移動
        TMP = TMP->next;
    }
    TMP->next = new_node;
    new_node->prev = TMP;
    return head; // 先頭ポインタを返す
}

// リストを出力する関数
void printDLL(Node* head) {
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

// k 個ごとのグループでリストを反転する関数
Node* revK(Node* head, int k) {
    if (!head)
        return NULL;
    head->prev = NULL;
    Node *TMP, *CURRENT = head, *newHead;
    int count = 0;
    // カウントが k 未満の間、ノードを反転していく
    while (CURRENT != NULL && count < k) {
        newHead = CURRENT;
        TMP = CURRENT->prev;
        CURRENT->prev = CURRENT->next;
        CURRENT->next = TMP;
        CURRENT = CURRENT->prev;
        count++;
    }
    if (count >= k) {
        // k 個以上反転できたら、続きのリストに対して再帰的に反転を行う
        head->next = revK(CURRENT, k);
    }
    return newHead;
}

int main() {
    Node* head;
    for (int i = 1; i <= 5; i++) {
        head = push(head, i);
    }
    cout << "Original List : ";
    printDLL(head);
    cout << "\nModified List : ";
    int k = 3;
    head = revK(head, k);
    printDLL(head);
}

実行結果

Original List : 1 2 3 4 5
Modified List : 3 2 1 5 4

コードの解説

revK 関数では、リストを走査しながらカウントが k 未満である間、各ノードの prev と next を入れ替えることで反転を行っています。

たとえば、リストが「1 2 3 4 5」で k = 3 の場合を考えてみましょう。最初の 3 要素は「3 2 1」と反転されますが、このままだと元の先頭だった「1」の next が NULL を指したままになってしまいます。しかし「1」の次には、これから反転される「4 5」のグループがつながる必要があります。

そこで、k 個のノードを反転し終えた時点で再帰呼び出しを行い、その戻り値（次のグループの反転結果の先頭）を head->next に代入することで、グループ同士を正しく連結しています。この if 文による条件分岐と再帰呼び出しが、このアルゴリズムのポイントです。

計算量

• 時間計算量：O(n) — 各ノードを一度だけ処理します。
• 空間計算量：O(n / k) — 再帰呼び出しの深さに依存します。

まとめ

この記事では、再帰を用いて双方向連結リストを指定されたサイズ k のグループごとに反転する問題を解きました。C++ による実装例に加えて、ポインタのつなぎ替えや再帰呼び出しの仕組みについても詳しく解説しました。同じロジックは C、Java、Python など他の言語でも同様に実装できますので、ぜひ自分でも書いてみてください。