【C++】再帰を使ってリンクリストの交互ノードを出力する方法

リンクリスト（連結リスト）とは

リンクリストは、各要素（ノード）をメモリ上の連続しない領域に格納できる線形データ構造です。各ノードにはデータ本体と、次のノードを指すポインタが含まれており、ポインタをつなぐことで一連のリストとして扱うことができます。

問題の概要

今回は、与えられたリンクリストを走査し、交互（ひとつおき）のノードだけを出力するプログラムを作成します。具体的には、1番目・3番目・5番目…というように、奇数番目の要素のみを順に出力していきます。

入出力例

入力 : 2 -> 4 -> 1 -> 67 -> 48 -> 90
出力 : 2 -> 1 -> 48

解説：先頭から数えて1番目・3番目・5番目の要素である「2」「1」「48」が出力されています。

フラグ変数を使った基本的なアプローチ

もっともシンプルな方法は、初期値が0のフラグ変数を用意し、ノードをたどりながら値を出力するかどうかを切り替えるやり方です。

• フラグが0のとき → ノードの値を出力し、フラグを1に変更する
• フラグが1のとき → 値は出力せず、フラグを0に戻す

この操作をリストの終端まで繰り返すことで、ひとつおきにノードの値が表示されます。

サンプルコード（反復処理版）

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

struct Node {
    int data;
    struct Node* next;
};

void printAlternateNode(struct Node* head){
    int flag = 0;
    while (head != NULL) {
        if (flag == 0){
            printf(" %d ", head->data);
            flag = 1;
        }
        else
            flag = 0;
        head = head->next;
    }
}

void insertNode(struct Node** head_ref, int new_data){
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

int main(){
    struct Node* head = NULL;
    insertNode(&head, 23);
    insertNode(&head, 4);
    insertNode(&head, 98);
    insertNode(&head, 5);
    insertNode(&head, 71);
    printAlternateNode(head);
    return 0;
}

出力結果

71  98  23

このプログラムでは、insertNode 関数が新しいノードを常にリストの先頭に挿入するため、挿入時の順序（23 → 4 → 98 → 5 → 71）と逆向きの並びになり、結果として「71 98 23」が出力されます。

再帰を使った実装

同じ問題は再帰を使っても解けます。現在のノードの値を出力した後、「次の次」のノードに対して自分自身を呼び出すことで、交互の出力を自然に実現できます。ここではC++らしい書き方として、フラグを引数で渡す方式を採用しました。

C++による再帰版コード

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

// 交互ノードを再帰的に出力する関数
void printAlternateNode(Node* head, bool flag = true){
    if (head == NULL)
        return;
    if (flag)
        cout << head->data << " ";
    printAlternateNode(head->next, !flag);
}

void insertNode(Node** head_ref, int new_data){
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

int main(){
    Node* head = NULL;
    insertNode(&head, 23);
    insertNode(&head, 4);
    insertNode(&head, 98);
    insertNode(&head, 5);
    insertNode(&head, 71);
    printAlternateNode(head); // 出力：71 98 23
    return 0;
}

再帰版では、呼び出しごとにフラグ !flag を渡して真偽を反転させるため、静的変数やループなしで交互出力が実現できます。ロジックが非常に簡潔になるのが大きなメリットです。

計算量について

• 時間計算量：O(n) ― リンクリストを一度だけ走査すればよいため、どちらの実装でも同様です。
• 空間計算量：反復版はO(1)。一方、再帰版は呼び出しごとにスタックフレームが必要なため、最大でO(n)のメモリを消費します。

まとめ

リンクリストの交互ノードの出力は、フラグ変数による反復処理でも再帰でも簡単に実装できます。反復版は余分なメモリを使わず大規模なリストにも安全で、再帰版はコードが簡潔で読みやすいのが魅力です。リストのサイズや要件に応じて、適切な実装を選択するとよいでしょう。