C言語の再帰を使って連結リストの末尾からk個のノードを表示する方法

本記事では、再帰（リカーシブ）アプローチを用いて、連結リスト（リンクリスト）の末尾からk個のノードを表示する方法を解説します。

再帰的アプローチとは、関数が終了条件を満たすまで自分自身を繰り返し呼び出し、その過程で結果を保持していく手法のことです。連結リストは前方へのポインタしか持たないため、末尾側から処理を行いたい場合には再帰が特に有効です。

例えば、リストが 29、34、43、56、88 というノードを持っており、k の値が 2 である場合、出力は末尾から 2 個のノード、つまり「88」と「56」になります。

実行例

連結リスト: 29->34->43->56->88
入力: 2
出力: 88 56

再帰による処理の流れ

再帰関数は、まずリストの終端（NULL）まで再帰的に進みます。その後、呼び出しスタックを巻き戻しながらカウントを 1 ずつ増やしていき、カウントが k 以内になったノードのみを表示します。これにより、結果としてリストの末尾から k 個のノードが出力される仕組みです。

アルゴリズム

START
    Step 1 -> 構造体型のノード変数を作成
        int型の data を宣言
        node型へのポインタ *next を宣言
    Step 2 -> 関数 node* get(int data) を宣言
        malloc関数で newnode を作成
        newnode->data = data を設定
        newnode->next = NULL を設定
        newnode を返す
    Step 3 -> 関数 void lastval(node* head, int* count, int k) を宣言
        IF !head ならば
            Return
        lastval(head->next, count, k) を呼び出す
        count をインクリメント
        IF (count <= k) ならば
            head->data を表示
    Step 4 -> main() 内で
        node* head = get(11) により head を生成
        k と count を 0 に初期化
        lastval(head, &count, k) を呼び出す
STOP

C言語での実装例

以下のコードは、上記アルゴリズムをC言語で実装したものです。C言語には参照渡し（C++の int&）がないため、カウント変数はポインタ経由で渡している点に注意してください。

#include <stdio.h>
#include <stdlib.h>

// ノードの構造体定義
struct node {
    int data;
    struct node* next;
};

// 新しいノードを生成する関数
struct node* get(int data) {
    struct node* newnode = (struct node*)malloc(sizeof(struct node));
    newnode->data = data;
    newnode->next = NULL;
    return newnode;
}

// 末尾からk個のノードの値を表示する関数
void lastval(struct node* head, int* count, int k) {
    if (!head)
        return;
    lastval(head->next, count, k);   // まず末尾まで再帰的に進む
    (*count)++;                      // 戻りながらカウントを増やす
    if (*count <= k)
        printf("%d ", head->data);   // k個目までのノードを表示
}

int main() {
    // リストへ要素を挿入
    struct node* head = get(11);
    head->next = get(243);
    head->next->next = get(321);
    head->next->next->next = get(421);
    head->next->next->next->next = get(522);

    int k = 2, count = 0;
    printf("リストの末尾 %d 個のノード : ", k);

    // 末尾のk個のノードを表示
    lastval(head, &count, k);
    return 0;
}

実行結果

上記のプログラムを実行すると、次のような出力が得られます。

リストの末尾 2 個のノード : 522 421

計算量について

このアルゴリズムではリスト全体を一度走査するため、時間計算量は O(n) となります。また、再帰呼び出しの深さがリストの長さに比例するため、コールスタック分の空間計算量も O(n) かかる点に留意してください。