【C++】連結リスト内の特定の整数（int）の出現回数をカウントする関数の作成方法

問題の概要

この記事では、C++の連結リスト（リンクリスト）を扱います。与えられた連結リストの中に、特定の整数（int型）が出現する回数を数える関数を作成するのが課題です。

まずは具体例で問題を確認してみましょう。

入力

連結リスト： 10 → 50 → 10 → 20 → 100 → 10 ／ 探す値： 10

出力

3

説明：数値「10」は連結リスト内に合計3回出現しています。

解法の考え方

この問題の解法はとてもシンプルです。連結リストを先頭から順番に走査し、現在のノードの値が探している数値と一致したらカウンターを+1するだけでOKです。

連結リストのノードをたどる方法には「反復（イテレーション）」と「再帰」の2通りがあります。以下では、それぞれの手法による実装例を紹介します。

方法1：反復（whileループ）を使った解法

#include <iostream>
using namespace std;

class Node {
public:
    int data;      // ノードが保持するデータ
    Node* next;    // 次のノードへのポインタ
};

// リストの先頭に新しいノードを挿入する関数
void push(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 countInt(Node* head, int search_for) {
    Node* current = head;
    int intCount = 0;
    while (current != NULL) {
        if (current->data == search_for)
            intCount++;
        current = current->next;
    }
    return intCount;
}

int main() {
    Node* head = NULL;
    push(&head, 10);
    push(&head, 40);
    push(&head, 10);
    push(&head, 50);
    push(&head, 20);
    push(&head, 90);
    push(&head, 10);

    cout << "連結リストにおける10の出現回数は "
         << countInt(head, 10) << " 回です";
    return 0;
}

実行結果：

連結リストにおける10の出現回数は 3 回です

補足：push()は常にリストの先頭へ挿入するため、main()で実際に構築されるリストは「10 → 90 → 20 → 50 → 10 → 40 → 10」という順序になります。いずれにせよ「10」は3回含まれているため、結果は3となります。

方法2：再帰を使った解法

再帰版では、グローバル変数に頼らず「残りのリストでのカウント結果」を返り値として受け取る形にすると、より安全でスマートな実装になります。

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

void push(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 countInt(Node* head, int key) {
    // ベースケース：リストの終端に到達したら0を返す
    if (head == NULL)
        return 0;
    // 一致していれば1、不一致なら0を加算して残りを再帰的に処理
    return (head->data == key ? 1 : 0) + countInt(head->next, key);
}

int main() {
    Node* head = NULL;
    push(&head, 10);
    push(&head, 40);
    push(&head, 10);
    push(&head, 50);
    push(&head, 20);
    push(&head, 90);
    push(&head, 10);

    cout << "連結リストにおける10の出現回数は "
         << countInt(head, 10) << " 回です";
    return 0;
}

実行結果：

連結リストにおける10の出現回数は 3 回です

計算量の目安

• 時間計算量：どちらの方法も全ノードを一度ずつ訪問するため O(n)（nはノード数）。
• 空間計算量：反復版は O(1)。再帰版は呼び出しスタックの分だけ O(n) のメモリを消費。

長いリストを扱う場合やスタックオーバーフローのリスクを避けたい場面では、反復版の利用が推奨されます。

まとめ

連結リスト内の特定の値の出現回数をカウントするには、リストを先頭から順にたどり、一致するノードを数えるだけで実現できます。反復・再帰どちらでも同じ結果が得られますが、追加メモリ不要で安全な反復版が実用上はおすすめです。