C++で連結リストを反転する方法【反復・スタック・再帰の3つのアプローチ】

この記事では、C++を使って単方向リンクリスト（片方向連結リスト）を反転する方法を解説します。目標は、与えられた連結リストのノードのつながりを逆向きに並べ替える関数を実装することです。

入力：
連結リスト :
1->2->3->4->NULL

出力：
関数の処理後 :
4->3->2->1->NULL

解決のためのアプローチ

連結リストを反転する方法はいくつかあります。最も直感的なのは、リストを先頭から順に走査しながら、その場でポインタをつなぎ替えていくというシンプルな手法です。本記事では、次の3つのアプローチを紹介します。

• シンプルなアプローチ（反復処理）：リストを走査しながら直接リンクを付け替える
• スタックを使うアプローチ：ノードを一旦スタックに積んでから取り出す
• 再帰を使うアプローチ：呼び出しスタックを利用して反転を行う

1. シンプルなアプローチ（反復処理）

まず基本となるのが、リストを先頭から順番にたどりながら、各ノードのnextポインタを前のノードへ向ける方法です。「現在のノード」「前のノード」「次のノード」の3つのポインタを使い分けることで、余分なメモリをほとんど使わずに反転できます。

実装例

#include<bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node* next;
    Node(int data) {
        this->data = data;
        next = NULL;
    }
};
struct LinkedList {
    Node* head;
    LinkedList() { head = NULL; }
    // リンクリストを反転する関数
    void reverse() {
        auto curr = head;      // 現在のノード
        Node* prev = NULL;     // 前のノード
        while(curr) {
            auto temp = curr -> next; // 次のノードを退避
            curr -> next = prev;      // リンクを逆方向へ付け替え
            prev = curr;
            head = prev;
            curr = temp;
        }
    }
    // リンクリストを表示する関数
    void print() {
        struct Node* temp = head;
        while (temp != NULL) {
            cout << temp->data << " ";
            temp = temp->next;
        }
    }
    // 先頭にノードを挿入する関数
    void push(int data) {
        Node* temp = new Node(data);
        temp->next = head;
        head = temp;
    }
};
int main() {
    LinkedList list;
    list.push(20);
    list.push(4);
    list.push(15);
    list.push(85);
    list.print();
    list.reverse();
    cout << "\n";
    list.print();
}

出力結果

85 15 4 20
20 4 15 85

この方法では、リストを一度だけ走査しながらその場でリンクを付け替えています。時間計算量は O(N)（Nはリストのサイズ）、追加のメモリ使用量は O(1) であるため、最も効率的で実用的な方法です。

2. スタックを使ったアプローチ

次に、スタック（LIFO構造）を活用した方法を見てみましょう。すべてのノードをスタックに格納した後、スタックの特性「後入れ先出し」を利用してノードを取り出すことで、自然と逆順のリストが組み上がります。

実装例

#include<bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node* next;
    Node(int data) {
        this->data = data;
        next = NULL;
    }
};
struct LinkedList {
    Node* head;
    LinkedList() { head = NULL; }
    // リンクリストを反転する関数
    void reverse() {
        auto curr = head;      // 現在のノード
        Node* prev = NULL;     // 前のノード
        stack<Node *> s;
        while(curr) {
            s.push(curr);          // 全ノードをスタックに積む
            curr = curr -> next;
        }
        prev = s.top();
        head = prev;           // 最後のノードが新しいheadになる
        s.pop();
        while(!s.empty()) {
            auto temp = s.top();
            s.pop();
            prev -> next = temp;   // 取り出した順につなぎ直す
            prev = temp;
        }
        prev -> next = NULL;   // 末尾のnextをNULLに設定
    }
    // リンクリストを表示する関数
    void print() {
        struct Node* temp = head;
        while (temp != NULL) {
            cout << temp->data << " ";
            temp = temp->next;
        }
    }
    // 先頭にノードを挿入する関数
    void push(int data) {
        Node* temp = new Node(data);
        temp->next = head;
        head = temp;
    }
};
int main() {
    LinkedList list;
    list.push(20);
    list.push(4);
    list.push(15);
    list.push(85);
    list.print();
    list.reverse();
    cout << "\n";
    list.print();
}

出力結果

85 15 4 20
20 4 15 85

コードの解説

このアプローチでは、リストを走査しながら全ノードをスタックに格納し、その後スタックから順に取り出してリンクを張り直すことでリストを反転しています。時間計算量は O(N) ですが、すべてのノードをスタックに保存するため、追加のメモリとして O(N) が必要になる点に注意してください。また、スタックを使って処理できるということは、同じ仕組みを持つ再帰でも同様の実装が可能です。そこで次に再帰版を見ていきましょう。

3. 再帰を使ったアプローチ

再帰呼び出しは内部的にスタックを使用するため、先ほどのスタックによるアプローチと同じ発想を、より簡潔なコードで実現できます。リストの末尾まで再帰的に進み、戻りながらリンクを付け替えていくのがポイントです。

実装例

#include<bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node* next;
    Node(int data) {
        this->data = data;
        next = NULL;
    }
};
struct LinkedList {
    Node* head;
    LinkedList() { head = NULL; }
    // 再帰的にリストを反転する関数
    void rreverse(Node *curr, Node *prev) {
        if(curr == NULL) {
            head = prev;       // 新しいheadを設定
            return;
        }
        rreverse(curr -> next, curr); // 先に末尾まで進む
        curr -> next = prev;          // 戻りながらリンクを逆方向へ
        prev -> next = NULL;
    }
    void reverse() {
        auto curr = head;      // 現在のノード
        Node* prev = NULL;     // 前のノード
        rreverse(curr -> next, curr);
    }
    // リンクリストを表示する関数
    void print() {
        struct Node* temp = head;
        while (temp != NULL) {
            cout << temp->data << " ";
            temp = temp->next;
        }
    }
    // 先頭にノードを挿入する関数
    void push(int data) {
        Node* temp = new Node(data);
        temp->next = head;
        head = temp;
    }
};
int main() {
    LinkedList list;
    list.push(20);
    list.push(4);
    list.push(15);
    list.push(85);
    list.print();
    list.reverse();
    cout << "\n";
    list.print();
}

出力結果

85 15 4 20
20 4 15 85

この方法も基本的な考え方は同じですが、ループの代わりに再帰呼び出しで処理しています。時間計算量は O(N) です。ただし、再帰の深さがリストの長さに比例するため、非常に大きなリストではスタックオーバーフローのリスクがある点に留意してください。

まとめ

この記事では、単方向リンクリストを反転する問題を取り上げ、反復処理・スタック・再帰の3つのアプローチとそれぞれのC++実装を紹介しました。どの方法も時間計算量はO(N)ですが、メモリ効率やコードの読みやすさには違いがあります。実務では追加メモリ不要の反復処理が最も推奨されます。なお、同じロジックはC、Java、Pythonなど他の言語でも同様に実装可能です。この記事が皆さんの学習の一助になれば幸いです。