C++で連結リストの末尾N個のノードの積を求める方法

連結リスト（リンクリスト）に複数の要素が格納されている場合を考えてみましょう。この記事では、リストの末尾からN個の要素を取り出し、それらの積（掛け算の結果）を求める方法を解説します。Nの値はあらかじめ与えられているものとします。

例えば、連結リストが [5, 7, 3, 5, 6, 9] という構成で、n = 3 が与えられた場合、末尾の3つの要素は 5、6、9 となるため、計算結果は 5 × 6 × 9 = 270 になります。

アルゴリズムの考え方

この問題の解き方は非常にシンプルです。連結リストは基本的に先頭から順方向にしか辿れないため、スタック（stack）を活用します。手順は以下の通りです。

1. リストを先頭から走査し、各要素の値を順番にスタックへプッシュしていく
2. すべての要素をスタックに入れ終えたら、スタックの先頭（リストの末尾の要素に相当）から順にN個取り出す
3. 取り出した値を結果変数 prod（初期値は1）に掛けていき、N個分の処理が完了した時点で計算を終了する

この手法を使えば、逆方向のポインタを持たない片方向連結リストでも、末尾のN要素に簡単にアクセスできます。計算量はリストの長さに比例する O(N) となり、効率的に処理が行えます。

C++での実装例

#include<iostream>
#include<stack>
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 prodLastNElements(Node *start, int n) {
      if(n <= 0)
         return 0;
      stack<int> stk;
      long long res = 1;
      Node* temp = start;
      while (temp != NULL) {
         stk.push(temp->data);
         temp = temp->next;
      }
      while(n--){
         res *= stk.top();
         stk.pop();
      }
   return res;
}
int main() {
   Node *start = NULL;
   int arr[] = {5, 7, 3, 5, 6, 9};
   int size = sizeof(arr)/sizeof(arr[0]);
   int n = 3;
   for(int i = 0; i<size; i++){
      append(&start, arr[i]);
   }
   cout << "Product of last n elements: " << prodLastNElements(start, n);
}

実行結果

Product of last n elements: 270

上記のコードでは、Nodeクラスで連結リストの各ノードを表現し、append関数によってリストの末尾へ新しいノードを追加しています。中心的な処理を行うのは prodLastNElements 関数です。n が0以下の場合は0を返すガード処理も組み込まれており、不正な入力にも対応しています。また、要素数が多い場合や値が大きい場合でも桁あふれ（オーバーフロー）を防げるよう、結果は long long 型で保持している点もポイントです。