C++でスタックを使って連結リスト（リンクリスト）を反転する方法

連結リスト（リンクリスト）はメモリを動的に確保するデータ構造であり、スタックの実装にも活用されます。本記事では、C++を使用して連結リストを反転させるプログラムを紹介します。スタックの「後入れ先出し（LIFO）」という特性を利用することで、連結リストのノードを簡単に逆順へ並べ替えることができます。以下の手順に従うことで、期待通りの結果が得られます。

アルゴリズム

START
    Step 1: ノードポインタ型の空のスタックを作成する
    Step 2: リストを走査し、すべてのノードの値をスタックにプッシュする
    Step 3: 先頭ノードから再びリストを走査する
    Step 4: スタックのトップから値をポップする
    Step 5: 取り出した値を逆順につなぎ合わせる
    Step 6: 結果を出力する
STOP

スタックは最後に格納した要素が最初に取り出される構造のため、連結リストの値を順にプッシュしていき、その後ポップしていくだけで自然と逆順の並びが得られます。上記のアルゴリズムに基づき、以下のC++コードを作成しました。ここでは stdlib.h ヘッダファイルが重要な役割を担っており、malloc() による動的メモリ確保など、必要な機能を提供しています。

サンプルコード

#include <iostream>
#include <stdlib.h>
using namespace std;
struct linked_list {
    int data;
    struct linked_list *next;
};
int stack[30], top = -1;
struct linked_list* head = NULL;
int printfromstack(int stack[]) {
    cout<<"\nStack after Reversal::";
    while(top>=0) {
        cout<<stack[top--]<<" ";
    }
}
int push(struct linked_list** head, int n) {
    struct linked_list* newnode = (struct linked_list*)malloc(sizeof(struct linked_list));
    newnode->data = n;
    newnode->next = (*head);
    (*head) = newnode;
}
int intostack(struct linked_list* head) {
    cout<<"Linked list::";
    while(head!=NULL) {
        printf("%d ", head->data);
        stack[++top] = head->data;
        head = head->next;
    }
}
int main(int argc, char const *argv[]) {
    push(&head, 7);
    push(&head, 20);
    push(&head, 3);
    push(&head, 40);
    intostack(head);
    printfromstack(stack);
    return 0;
}

このコードの処理の流れは以下のとおりです。
まず push() 関数が、新しいノードを動的に確保してリストの先頭に追加します。次に intostack() 関数が、連結リストを先頭から走査しながら各ノードの値を配列で実装したスタックへ格納します。最後に printfromstack() 関数が、スタックのトップから順に値をポップして表示することで、反転後の並びを出力します。これらの一連の処理は main() 関数から呼び出されて実行されます。

出力結果

Linked list:: 40 3 20 7
Stack after Reversal::7 20 3 40

実行結果を見ると、元の連結リストは「40 → 3 → 20 → 7」の順で格納されていますが、スタック経由で反転処理を行った結果、「7 → 20 → 3 → 40」という逆順の出力が得られていることが確認できます。このように、スタックを利用した反転処理は実装がシンプルで理解しやすいのが特徴です。