Cプログラムで追加領域やリストの変更なしに連結リストを逆順に表示する方法

この課題は、連結リスト（リンクリスト）のノードを末尾から先頭に向かって表示するというものです。ただし、追加のメモリ領域を使用しないことが条件です。つまり、再帰呼び出しやスタックのような補助変数・データ構造を使わず、先頭ノードを指すヘッドポインタだけを利用して実現する必要があります。

例

入力：10 21 33 42 89
出力：89 42 33 21 10

連結リストを逆順に表示する方法はいくつか考えられます。例えば、以下のようなアプローチが挙げられます。

• 再帰的な手法：関数呼び出しのスタックを使用するため、O(n) の追加領域が必要になります。
• リスト自体を反転させる手法：元の連結リストに変更を加えてしまうため、条件を満たしません。
• スタックに要素を積んでから取り出す手法：O(n) の追加領域が必要になります。

これらの方法はいずれも O(1) を超える領域を消費してしまいます。

O(1) の領域で実現するアイデア

追加領域を O(1) 以内に抑えて結果を得るには、次の手順が有効です。

• まず、連結リスト内のノード数を数えます。
• 次に、i = n から 1 までループし、i 番目の位置にあるノードの値を順番に表示します。

この方法では、ノード総数 n を格納する変数とループカウンタ程度の固定領域しか使わないため、空間計算量は O(1) に抑えられます。一方で、各位置へのアクセスに毎回先頭からの走査が必要となるため、時間計算量は O(n²) になる点には注意が必要です。

アルゴリズム

START
Step 1 -> 構造体型のノード変数を作成する
    int data を宣言
    node 型ポインタ *next を宣言
Step 2 -> 関数 int get(struct node* head) を宣言
    変数 int count = 0 を宣言
    struct node *newme = head を宣言
    newme != NULL の間ループ
        count を 1 増やす
        newme = newme->next を設定
    ループ終了
    count を返す
Step 3 -> 関数 void push(node** headref, int newdata) を宣言
    malloc でメモリを確保
    newnode->data = newdata を設定
    newnode->next = (*headref) を設定
    (*headref) = newnode を設定
Step 4 -> 関数 int getN(struct node* head, int n) を宣言
    struct node* cur = head を宣言
    i = 0 から i < n-1 && cur != NULL の間 cur = cur->next でループ
    cur->data を返す
Step 5 -> 関数 void reverse(node *head) を宣言
    int n = get(head) を宣言
    i = n から i >= 1 まで i-- でループ
        getN(head, i) の結果を表示
Step 6 -> main() 内で
    node* head = NULL としてリストを作成
    push(&head, 89) などで要素を挿入
    reverse(head) を呼び出す
STOP

C言語による実装例

#include<stdio.h>
#include<stdlib.h>
// ノード構造体
struct node {
    int data;
    struct node* next;
};
void push(struct node** headref, int newdata) {
    struct node* newnode = (struct node*) malloc(sizeof(struct node));
    newnode->data = newdata;
    newnode->next = (*headref);
    (*headref) = newnode;
}
int get(struct node* head) {
    int count = 0;
    struct node* newme = head;
    while (newme != NULL){
        count++;
        newme = newme->next;
    }
    return count;
}
int getN(struct node* head, int n) {
    struct node* cur = head;
    for (int i=0; i<n-1 && cur != NULL; i++)
        cur = cur->next;
    return cur->data;
}
void reverse(struct node *head) {
    int n = get(head);
    for (int i=n; i>=1; i--)
        printf("%d ", getN(head, i));
}
int main() {
    struct node* head = NULL; // 先頭ノードを作成
    push(&head, 89); // リストへ要素を追加
    push(&head, 42);
    push(&head, 33);
    push(&head, 21);
    push(&head, 10);
    reverse(head); // 逆順表示関数を呼び出し
    return 0;
}

実行結果

上記のプログラムを実行すると、次の出力が生成されます。

89 42 33 21 10

このように、リストの長さを事前に求めておき、後ろから順にノードを参照することで、追加のデータ構造やリストの改変なしに逆順表示を実現できます。メモリ制約が厳しい組み込みシステムなどで特に有効なテクニックです。