連結リストの末尾k個のノードを逆順に出力する方法【C言語・反復アプローチ】

本記事では、連結リスト（リンクリスト）の末尾からk個のノードを逆順に表示するプログラムを、反復アプローチ（繰り返し処理）を用いてC言語で実装する方法を解説します。

反復法とは、条件式が真（true）である限りループを繰り返し実行する手法のことです。再帰呼び出しを使わずにシンプルなループ処理だけで問題を解決できる点が特徴です。

例えば、リストが「29 → 34 → 43 → 56 → 88」というノードで構成されており、k = 2 が与えられた場合、出力は末尾から2つのノードである「56」と「88」になります。

入力例と出力例

Linked List: 29->34->43->56->88
Input: 2
Output: 56 88

リストの末尾k個の要素を取り出すには、スタックと同じ考え方（LIFO：後入れ先出し）が有効です。リストを先頭から走査しながら値を配列の後ろ側から順に格納していくことで、配列の先頭にはリストの末尾の要素が並びます。あとは配列の先頭からk個分だけ取り出せば、連結リストの末尾のノードを逆順に取得できます。

以下に、このアルゴリズムのC言語による実装を示します。

アルゴリズム

START
    Step 1 -> ノード構造体を作成する
        int型の data を宣言
        node型ポインタ *next を宣言
    Step 2 -> struct node* intoList(int data) を作成
        malloc で newnode を生成
        newnode->data = data を設定
        newnode->next = NULL を設定
        newnode を返す
    Step 3 -> void rev(struct node* head, int count, int k) を宣言
        struct node* temp1 = head を作成
        temp1 != NULL の間ループ
            count++
            temp1 = temp1->next
        ループ終了
        int array[count], temp2 = count, i を宣言
        temp1 = head を設定
        temp1 != NULL の間ループ
            array[--temp2] = temp1->data を設定
            temp1 = temp1->next を設定
        ループ終了
        i = 0 から i < k までループ
            array[i] を表示
        ループ終了
    Step 4 -> main() 内での処理
        struct node* head = intoList(9) でリストを作成
        k=3、count=0 を設定
        rev(head, count, k) を呼び出す
STOP

C言語での実装例

#include<stdio.h>
#include<stdlib.h>
// ノードの構造体
struct node {
    int data;
    struct node *next;
};
// 新しいノードを挿入する関数
struct node* intoList(int data) {
    struct node* newnode = (struct node*)malloc(sizeof(struct node));
    newnode->data = data;
    newnode->next = NULL;
    return newnode;
}
// ノードの要素を逆順に表示する関数
void rev(struct node* head,int count, int k) {
    struct node* temp1 = head;
    while(temp1 != NULL) {
        count++;
        temp1 = temp1->next;
    }
    int array[count], temp2 = count,i;
    temp1 = head;
    while(temp1 != NULL) {
        array[--temp2] = temp1->data;
        temp1 = temp1->next;
    }
    for(i = 0; i < k; i++)
    printf("%d ",array[i]);
}
int main() {
    printf("\nreverse of a list is : ");
    struct node* head = intoList(9); // リストへ要素を挿入
    head->next = intoList(76);
    head->next->next = intoList(13);
    head->next->next->next = intoList(24);
    head->next->next->next->next = intoList(55);
    head->next->next->next->next->next = intoList(109);
    int k = 3, count = 0;
    rev(head, count, k); // 逆順表示のための関数を呼び出し
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

reverse of a list is : 109 55 24

処理の流れのポイント

このプログラムでは、まず1回目の走査でリスト全体のノード数を数え、その後2回目の走査で各ノードの値を配列の末尾から先頭に向かって格納していきます。これにより、配列のインデックス0には元のリストの最後尾の要素が入るため、先頭からk個を出力するだけで「末尾k個のノードを逆順に表示する」という要件が実現できます。

計算量はリストを2回走査するため O(n)、補助記憶としてノード数分の配列を使用するため空間計算量も O(n) となります。再帰を使わないため、スタックオーバーフローの心配もなく、長いリストでも安全に動作するのが利点です。