【C言語】連結リストを実際には反転せずに逆順で表示する方法

この課題では、再帰関数を使用して、与えられた連結リスト（リンクリスト）を逆順に表示します。ポイントは、リストそのものを反転させるのではなく「逆順に表示する」だけである点です。つまり、ノードのつながりの順序は元のまま一切変わりません。

仕組みとしては、先頭ノードのアドレスを持つヘッドポインタが、リストの末尾ノードに格納されている NULL が見つかるまで次々と次のノードへ移動し、その後、呼び出しが戻りながら各ノードのデータを表示していきます。

実行例

Input: 29 34 43 56
Output: 56 43 34 29

まず、ノードをリストに挿入し、ポインタを挿入済みのノードに向けます。リストが完成したら、テンポラリ（temp）ポインタを先頭ノードで初期化し、末尾ノードは何も指していないため、ノードの next アドレスが NULL になるまで順に進めていきます。その後、末尾ノードからヘッドポインタに向かってリストを逆にたどることで、リストを実際に反転させることなく、逆順の内容を表示できます。

アルゴリズム

START
    Step 1 -> 構造体型のノード変数を作成する
        int 型の data を宣言
        ノード型のポインタ *next を宣言
    Step 2 -> 関数 void reverse(node* head) を宣言
        IF head == NULL ならば
            return
        reverse(head->next) を呼び出す
        head->data を表示する
    Step 3 -> 関数 void push(node** header, char newdata) を宣言
        malloc を使用してメモリを確保する
        newnode->data = newdata を設定
        newnode->next = (*header) を設定
        (*header) = newnode を設定
    Step 4 -> main() 内で
        node* head = NULL としてリストを作成
        push(&head, 56) で要素を挿入
        reverse(head) を呼び出す
STOP

C言語での実装例

以下のコードは、上記アルゴリズムのC言語による実装です。

#include<stdio.h>
#include<stdlib.h>
// ノード用の構造体を作成
struct node {
    int data;
    node* next;
};
// リスト内のデータを逆順に表示する関数
void reverse(node* head) {
    if (head == NULL)
        return;
    reverse(head->next);
    printf("%d ", head->data);
}
// ノードをリストに追加する関数
void push(node** header, char newdata) {
    struct node* newnode = (struct node*)malloc(sizeof(struct node));
    newnode->data = newdata;
    newnode->next = (*header);
    (*header) = newnode;
}
int main() {
    node* head = NULL;
    push(&head, 56); // 56 をリストに追加
    push(&head, 43);
    push(&head, 34);
    push(&head, 29);
    reverse(head);
    return 0;
}

解説：なぜ再帰で逆順表示できるのか？

再帰呼び出しでは、関数が自分自身を呼び出した時点ではまだ printf が実行されていません。まず再帰の最深部（NULL の判定）まで到達し、そこから呼び出しが戻る過程で各ノードのデータが順に表示されます。これは「後入れ先出し（LIFO）」のスタック構造を利用した手法であり、ポインタをつなぎ替えることなく、末尾から先頭へとデータを出力できます。計算量は O(n)、再帰に必要なスタック領域も O(n) となります。

出力結果

上記のプログラムを実行すると、以下の出力が得られます。

reverse of a linked list 56 43 34 29