C++で連結リストの交互ノードの合計を求める方法（反復法・再帰法）

問題概要

この記事では、連結リスト（リンクリスト）が与えられたときに、その交互ノード（0、2、4…番目のノード）の値の合計を求める方法を解説します。

連結リストとは、リンク（ポインタ）によって順次接続されたデータ構造の列です。各ノードはデータ本体と、次のノードを指す参照を持っています。

今回の課題は、連結リストのうち位置 0、2、4、6 … にあるノード、つまり先頭から1つおきのノードの値をすべて加算することです。

入出力例

入力：

4 → 12 → 10 → 76 → 9 → 26 → 1

出力：

24

説明：

交互ノードを取り出すと −
4 + 10 + 9 + 1 = 24

解決の考え方

この問題は、リストを先頭から順に走査しながら、加算対象のノードに出会ったらその値を合計に足していくことで解けます。「現在のノードが加算対象かどうか」を判定するために、bool型のフラグ変数を使用します。

実装方法には反復（ループ）による方法と再帰による方法の2通りがあります。以下、それぞれのコード例を見ていきましょう。

方法1：反復法（イテレーション）

whileループでリストをたどり、フラグがtrueのときだけノードの値を加算します。ノードを1つ進めるごとにフラグを反転させれば、自然に1つおきのノードだけが合計されます。

#include <iostream>
using namespace std;
struct Node {
    int data;
    struct Node* next;
};
void pushNode(struct Node** head_ref, int newData) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->next = (*head_ref);
    (*head_ref) = newNode;
}
int sumAlternateNodeIt(struct Node* head) {
    bool flag = true;
    int sum = 0;
    while (head != NULL){
        if (flag)
            sum += head->data;
        flag = !flag;
        head = head->next;
    }
    return sum;
}
int main(){
    struct Node* head = NULL;
    pushNode(&head, 54);
    pushNode(&head, 12);
    pushNode(&head, 87);
    pushNode(&head, 1);
    pushNode(&head, 99);
    pushNode(&head, 11);
    cout<<"交互ノードの合計は "<<sumAlternateNodeIt(head);
    return 0;
}

出力：

交互ノードの合計は 24

なお、pushNode関数は先頭への挿入を行うため、上記のコードではリストは 11 → 99 → 1 → 87 → 12 → 54 の順に構成されます。交互ノードは 11 + 1 + 12 = 24 となり、出力結果と一致します。

方法2：再帰法（リカージョン）

再帰版では、関数の引数に「合計値への参照」と「フラグ」を渡します。ノードがNULL（リストの終端）に達した時点で再帰を終了し、フラグがtrueのノードの値だけを加算していきます。

#include <iostream>
using namespace std;
struct Node {
    int data;
    struct Node* next;
};
void pushNode(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;
}
void sumAlternateNodeRec(struct Node* node, int& sum, bool flag = true){
    if (node == NULL)
        return;
    if (flag == true)
    sum += (node->data);
    sumAlternateNodeRec(node->next, sum, !flag);
}
int main(){
    struct Node* head = NULL;
    pushNode(&head, 54);
    pushNode(&head, 12);
    pushNode(&head, 87);
    pushNode(&head, 1);
    pushNode(&head, 99);
    pushNode(&head, 11);
    int sum = 0;
    sumAlternateNodeRec(head, sum, true);
    cout<<"交互ノードの合計は "<<sum;
    return 0;
}

出力：

交互ノードの合計は 24

計算量と使い分けのポイント

どちらの方法でも、リスト内の全ノードを一度ずつ訪問するため、時間計算量は O(n) です。一方、空間計算量は反復法では追加メモリが不要なため O(1)、再帰法では呼び出しスタックがリストの長さ分必要になるため O(n) となります。

非常に長い連結リストを扱う場合、再帰法ではスタックオーバーフローのリスクがあるため、実務では反復法を選ぶのが安全です。コードの簡潔さを重視する場面や、学習目的で再帰の動きを理解したい場合には、再帰法も有効な選択肢となります。