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

この記事では、片方向連結リスト（Singly Linked List）を扱い、リストを k個ずつのグループ に分けて反転する方法を解説します。

問題の概要

入力：1->2->3->4->5->6->7->8->NULL、K = 3
出力：3->2->1->6->5->4->8->7->NULL

入力：1->2->3->4->5->6->7->8->NULL、K = 5
出力：5->4->3->2->1->8->7->NULL

この問題に対して真っ先に思いつくアプローチは、リストを順番にたどりながら、部分リストの要素数が k に達した時点でその部分を反転し、これを最後まで繰り返すというものです。

解決のためのアプローチ

このアプローチでは、リスト全体を走査しながらカウンター変数を用いて部分リスト内の要素数を数えていきます。カウンターが k に達したら、その部分を反転します。残りのノードがある場合は、再帰的に同じ処理を呼び出すことで、次のグループも同様に反転していきます。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Node {
    public:
    int data;
    Node* next;
};
Node* reverse(Node* head, int k) {
    if (!head)
        return NULL;
    Node* curr = head;
    Node* next = NULL;
    Node* prev = NULL;
    int count = 0;
    // カウントがk未満の間、リストを反転する
    while (curr != NULL && count < k) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
        count++;
    }
    // リストがまだ終わっていなければ、再帰的にreverse関数を呼び出す
    if (next != NULL)
        head->next = reverse(next, k);
    return prev;
}
// リストにデータを追加する関数
void push(Node** head_ref, int new_data) {
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}
// 連結リストを出力する関数
void printList(Node* node) {
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
    cout << "\n";
}
int main() {
    Node* head = NULL;
    int k = 3; // 指定されたk
    push(&head, 8);
    push(&head, 7);
    push(&head, 6);
    push(&head, 5);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);
    cout << "元のリスト \n";
    printList(head);
    // この関数は新しいヘッドを返す
    head = reverse(head, k);
    cout << "反転後のリスト \n";
    printList(head);
    return (0);
}

実行結果

元のリスト
1 2 3 4 5 6 7 8
反転後のリスト
3 2 1 6 5 4 8 7

計算量について

このアプローチの時間計算量は O(N) です。ここで N は与えられたリストのサイズです。各ノードは一度だけ訪問されるため効率的であり、再帰を用いた実装になっています。この手法は、より大きな制約を持つ入力にも対応できます。

コードの解説

このアプローチでは、リストを走査しながら、カウンター変数が k 未満である間はノードのつながりを反転し続けます。カウンターが k に達すると、次のグループの反転処理を呼び出し、現在の部分リストの末尾ノードを、次に反転された部分リストの先頭ノードへ接続します。この一連の処理は再帰によって実現されています。

具体的には、reverse 関数は以下の手順で動作します。

1. 現在のヘッドから最大 k 個のノードを反転する。
2. 反転後の新しい先頭（prev）を返り値として保持する。
3. まだ処理されていないノード（next）が存在する場合、元のヘッドの next を再帰呼び出しの結果につなげる。

まとめ

この記事では、再帰を用いて連結リストを指定されたサイズのグループごとに反転する問題を解きました。C++によるプログラムの実装例と、その解法へのアプローチについても詳しく説明しました。同じロジックは C、Java、Python など他のプログラミング言語でも同様に実装できます。本記事が皆さんの学習の一助となれば幸いです。