【C++】循環リンクリストのノード値の合計を求める方法

この記事では、循環リンクリスト（Circular Linked List）が与えられたときに、すべてのノードの値の合計を求めるプログラムをC++で作成する方法を解説します。

やるべきことはシンプルで、リンクリストを構成する全ノードの値を順番に読み取り、それらを加算していくだけです。

前提知識：重要な定義

リンクリストとは

リンクリスト（連結リスト）とは、各データ（ノード）をポインタによるリンクで相互に接続したデータ構造の列です。配列と異なり、メモリ上の連続した領域を必要とせず、動的な挿入や削除に強いという特徴があります。

循環リンクリストとは

循環リンクリストはリンクリストの変形の一種で、先頭の要素が末尾の要素を指し、末尾の要素が先頭の要素を指すことで、リスト全体が環状につながっている構造です。片方向リンクリスト（Singly Linked List）でも双方向リンクリスト（Doubly Linked List）でも、同様に循環構造にすることができます。

問題例

具体的な入力と出力の例を見てみましょう。

入力

14 -> 1 -> 7 -> 9 -> 2 -> 6

出力

39

説明

合計 = 14 + 1 + 7 + 9 + 2 + 6 = 39

解決のアプローチ

この問題を解くには、リンクリストを一周するまで走査（トラバース）し、通過した各ノードの値を合計用の変数に加算していきます。そして、リスト全体の走査が完了した時点で合計値を返します。

循環リンクリストには終端（NULL）が存在しないため、通常のwhile文ではなくdo-while文を使い、「先頭ノードに戻ってきたかどうか」を終了条件にするのがポイントです。

アルゴリズム

1. ステップ1： 合計sumを0で初期化し、走査用ポインタsumPointerをhead（先頭ノード）に設定します。
2. ステップ2： sumPointerが再びheadに戻るまで、以下の処理を繰り返します。
   ステップ2.1： 現在のノードの値をsumに加算します（sum += sumPointer→value）。
   ステップ2.2： ポインタを次のノードへ進めます（sumPointer = sumPointer→next）。
3. ステップ3： 合計sumを返します。

C++での実装例

以下は、この解法を実装したサンプルプログラムです。

#include <iostream>
using namespace std;

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

// 循環リンクリストの先頭に新しいノードを追加する
void pushNode(struct Node** head_ref, int data) {
    struct Node* ptr1 = (struct Node*)malloc(sizeof(struct Node));
    struct Node* temp = *head_ref;
    ptr1->data = data;
    ptr1->next = *head_ref;
    if (*head_ref != NULL) {
        // 既存の末尾ノードを探し、そのnextを新ノードに向ける
        while (temp->next != *head_ref)
            temp = temp->next;
        temp->next = ptr1;
    } else {
        // リストが空の場合は自分自身を指す（1周する）
        ptr1->next = ptr1;
    }
    *head_ref = ptr1;
}

// 循環リンクリストのノード値の合計を計算する
int CalcSumCirList(struct Node* head) {
    struct Node* sumPointer = head;
    int sum = 0;
    if (head != NULL) {
        do {
            sum += sumPointer->data;
            sumPointer = sumPointer->next;
        } while (sumPointer != head);
    }
    return sum;
}

int main() {
    struct Node* head = NULL;
    pushNode(&head, 4);
    pushNode(&head, 7);
    pushNode(&head, 12);
    pushNode(&head, 1);
    pushNode(&head, 9);
    pushNode(&head, 6);
    cout<<"The sum of Circular linked list is "<<CalcSumCirList(head);
    return 0;
}

実行結果

The sum of Circular linked list is 39

まとめ

循環リンクリストのノード値の合計を求める処理は、時間計算量O(n)・空間計算量O(1)で実現できます。終端がNULLではない循環リスト特有の構造に対応するため、do-while文を使って「先頭ノードに戻った時点」でループを抜けるのが実装のポイントです。ぜひ本記事のコードを参考に、実際に動かしてみてください。