C++で連結リストの先頭k個のノードの積を求める方法

連結リストに複数の要素が格納されている場合を考えます。このとき、先頭からk個の要素の積（乗算結果）を求める必要があります。kの値もあらかじめ与えられているものとします。

例えば、連結リストが [5, 7, 3, 5, 6, 9] で、k = 3 である場合、計算結果は 5 × 7 × 3 = 105 となります。

アルゴリズムの考え方

処理の手順は非常にシンプルです。連結リストを左（先頭）から順に走査し、現在のノードの値を結果変数に掛けていきます。結果変数の初期値は 1 に設定しておきます。k個の要素を処理し終えた時点で走査を終了し、その時点での積を返します。

このアルゴリズムの計算量は O(k) であり、連結リスト全体を走査する必要がないため、リストが長い場合でも効率的に処理できます。また、積が大きな値になる可能性を考慮し、結果は long long 型で保持しています。

C++での実装例

#include<iostream>
#include<cmath>
using namespace std;

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

Node* getNode(int data) {
    Node *newNode = new Node;
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void append(struct Node** start, int key) {
    Node* new_node = getNode(key);
    Node *p = (*start);
    if (p == NULL) {
        (*start) = new_node;
        return;
    }
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = new_node;
}

long long prodFirstKElements(Node *start, int k) {
    long long res = 1;
    int count = 0;
    Node* temp = start;
    while (temp != NULL && count != k) {
        res *= temp->data;
        count++;
        temp = temp->next;
    }
    return res;
}

int main() {
    Node *start = NULL;
    int arr[] = {5, 7, 3, 5, 6, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    for (int i = 0; i < n; i++) {
        append(&start, arr[i]);
    }
    cout << "Product of first k elements: " << prodFirstKElements(start, k);
}

実行結果

Product of first k elements: 105

コードの解説

このプログラムは以下の構成要素で成り立っています。

Nodeクラス： 連結リストの各ノードを表します。整数値を格納する data フィールドと、次のノードを指す next ポインタを持ちます。

append関数： リストの末尾に新しいノードを追加します。リストが空の場合は、新しいノードを先頭として設定します。

prodFirstKElements関数： 中核となる処理を行う関数です。結果変数 res を 1 で初期化し、カウンタ count が k に達するまで、またはリストの終端に到達するまで、各ノードの値を res に掛け続けます。

main関数： 配列の要素を連結リストに追加し、k = 3 として prodFirstKElements 関数を呼び出して結果を表示します。

注意点

リストの要素数がkより少ない場合でも、この実装はリストの終端（NULL）をチェックしているため、安全に動作し、存在する全要素の積を返します。また、要素の値が大きい場合や要素数が多い場合は、オーバーフローを防ぐために long long 型を使用している点にも注目してください。