【C++】リンクリスト内の偶数ノード・奇数ノードの合計を求める方法

この問題では、連結リスト（リンクリスト）が与えられ、偶数の値を持つノードの合計と奇数の値を持つノードの合計をそれぞれ求めることが課題となります。

問題の例

具体的な入力と出力を見て、問題のイメージをつかみましょう。

入力：連結リスト：3 → 2 → 5 → 7 → 1 → 9
出力：evenSum = 2 ; oddSum = 25

説明：

evenSum = 2（偶数は 2 のみ）
oddSum = 3 + 5 + 7 + 1 + 9 = 25

解決アプローチ

最もシンプルな解法は、リンクリストを先頭から順に走査し、各ノードの値が偶数か奇数かを判定しながら、対応する合計値に加算していく方法です。リスト全体を一度だけ走査すればよいため、非常に効率的です。

アルゴリズム

• ステップ1 − リンクリストを先頭から順に走査します。

  • ステップ1.1 − 現在のノードの値が偶数であれば、evenSum に加算します。

  • ステップ1.2 − 現在のノードの値が奇数であれば、oddSum に加算します。

• ステップ2 − 最後に evenSum と oddSum を出力（または返却）します。

実装例

以下は、この解法の動作を示すC++プログラムです。

#include <iostream>
using namespace std;

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

void insertNode(Node** root, int item) {
    Node* ptr = *root;
    Node* temp = new Node;
    temp->data = item;
    temp->next = NULL;
    if (*root == NULL) {
        *root = temp;
    } else {
        while (ptr->next != NULL)
            ptr = ptr->next;
        ptr->next = temp;
    }
}

// 偶数かどうかを判定する関数
bool isEven(int a) {
    return (a % 2 == 0);
}

void findEvenAndOddSum(Node* root) {
    int evenSum = 0, oddSum = 0;
    Node* node = root;
    while (node != NULL) {
        if (isEven(node->data))
            evenSum += node->data;
        else
            oddSum += node->data;
        node = node->next;
    }
    cout << "偶数値を持つノードの合計: " << evenSum << endl;
    cout << "奇数値を持つノードの合計: " << oddSum << endl;
}

int main() {
    Node* root = NULL;
    insertNode(&root, 3);
    insertNode(&root, 2);
    insertNode(&root, 5);
    insertNode(&root, 7);
    insertNode(&root, 1);
    insertNode(&root, 9);
    insertNode(&root, 6);
    findEvenAndOddSum(root);
    return 0;
}

実行結果

偶数値を持つノードの合計: 8
奇数値を持つノードの合計: 25

このプログラムでは、リスト 3 → 2 → 5 → 7 → 1 → 9 → 6 を扱っています。偶数は 2 と 6 なので evenSum = 2 + 6 = 8 となり、奇数は 3 + 5 + 7 + 1 + 9 で oddSum = 25 となります。

注意点

偶数判定には必ず a % 2 == 0 を使うようにしましょう。return (a % 2); のように書いてしまうと、剰余が 0 以外のとき（＝奇数のとき）に真を返すため、偶数と奇数の判定が逆になり、誤った結果が出力されてしまいます。

計算量

• 時間計算量： O(n) ― リストを一度だけ走査するため、要素数 n に比例します。

• 空間計算量： O(1) ― 合計値を保持する変数のみを使用し、追加のメモリは不要です。