C++でリンクリスト内の各ノードの小さい方の要素を合計する方法

この問題では、2つの整数値（X と Y）と次のノードへのポインタを持つノードから構成されるリンクリストが与えられます。求めるのは、各ノードにおける小さい方の値をすべて合計した結果です。

リンクリストの各ノードには X と Y という2つの値が格納されています。プログラムは各ノードごとに X と Y を比較して小さい方を選び、それらをすべて足し合わせた値を出力します。

入力例

(5,2)->(7,9)->(6,3)->(36,24)->(19,26)->null

出力例

55

計算の流れ

各ノードで X と Y のうち小さい方の値を取り出します。

node1 - 最小値 = 5
node2 - 最小値 = 7
node3 - 最小値 = 3
node4 - 最小値 = 24
node5 - 最小値 = 19
合計 = 55

この問題は、非常にシンプルなアプローチで解くことができます。リストを先頭から順に走査しながら、各ノードの X と Y を比較して小さい方を求め、それを合計用の変数に加えていきます。リストの終端に到達した時点で合計値を返せば完了です。

アルゴリズム

初期化 − sum = 0

ステップ1 − リストを走査し、以下の処理を行います。

ステップ1.1 − head→X と head→Y のうち小さい方を求めます。

ステップ1.2 − 求めた最小値を sum に加算します。

ステップ2 − 走査が終わったら sum を返します。

C++による実装例

以下は、上記アルゴリズムの動作を示すC++プログラムです。

#include <iostream>
using namespace std;
struct Node {
    int X;
    int Y;
    Node* next;
};
void addNode(Node** head, int x, int y){
    Node* ptr = *head;
    Node* temp = new Node();
    temp->X = x;
    temp->Y = y;
    temp->next = NULL;
    if (*head == NULL)
        *head = temp;
    else {
        while (ptr->next != NULL)
            ptr = ptr->next;
        ptr->next = temp;
    }
}
int findMinSum(Node* head){
    int sum = 0;
    while (head != NULL) {
        sum += min(head->X , head->Y);
        head = head->next;
    }
    return sum;
}
int main(){
    Node* head = NULL;
    addNode(&head, 5, 2);
    addNode(&head, 7, 9);
    addNode(&head, 6, 3);
    addNode(&head, 36, 24);
    addNode(&head, 19, 26);
    cout<<"リンクリスト内のノードの小さい方の要素の合計は "<<findMinSum(head)<<endl;
    return 0;
}

実行結果

リンクリスト内のノードの小さい方の要素の合計は 55