単方向リンクリストの全ノードの積を求めるアルゴリズムとC言語実装

n個のノードで構成される単方向リンクリスト(片方向連結リスト)が与えられたとき、すべてのノードが保持する値の積を求めて出力するのがこの記事のテーマです。プログラムは先頭ノードからスタートし、リストの終端を示すNULLに到達するまで各ノードを順番にたどります。

例

入力 -: 1 2 3 4 5
出力 -: 120

上記の例では、先頭ノードから順に1、2、3、4、5のすべてのノードをたどり、それぞれの値を掛け合わせています。したがって積は 1×2×3×4×5 = 120 となります。

使用するアプローチ

以下の手順で全ノードの積を計算します。

• node型の一時ポインタ(ここでは temp とします)を用意する
• temp ポインタに、head ポインタが指す先頭ノードへの参照を代入する
• temp がNULLでない間、temp を temp->next に移動しながらループを続ける
• ループ内で product = product * (temp->data) を実行し、積を逐次更新する

アルゴリズム

開始
ステップ1 -> ノードの構造体を作成し、temp・next・head を構造体ノードへのポインタとして定義する
    struct node
        int data
        struct node *next, *head, *temp
    終了
ステップ2 -> リストにノードを挿入する関数を宣言する
    void insert(int val)
        struct node* newnode = (struct node*)malloc(sizeof(struct node))
        newnode->data = val
        IF head == NULL
            head = newnode
            head->next = NULL
        終了
        ELSE
            temp = head
            LOOP WHILE temp->next != NULL
                temp = temp->next
            終了
        newnode->next = NULL
        temp->next = newnode
    終了
ステップ3 -> リストを表示する関数を宣言する
    void display()
        IF head == NULL
            Print "no node"
        終了
        ELSE
            temp = head
            LOOP WHILE temp != NULL
                Print temp->data
                temp = temp->next
            終了
        終了
ステップ4 -> 全ノードの積を求める関数を宣言する
    void product_nodes()
        int product = 1 を宣言
        temp = head
        LOOP WHILE temp != NULL
            product = product * (temp->data)
            temp = temp->next
        終了
        Print product
ステップ5 -> main() 内で
    構造体ノードを作成する
    insert() を呼び出してノードを順次挿入する
    display() を呼び出してリストを表示する
    product_nodes() を呼び出して全ノードの積を求める
停止

C言語による実装例

#include<stdio.h>
#include<stdlib.h>
// ノードの構造体
struct node{
    int data;
    struct node *next;
}*head,*temp;
// リストにノードを挿入する関数
void insert(int val){
    struct node* newnode = (struct node*)malloc(sizeof(struct node));
    newnode->data = val;
    newnode->next = NULL;
    if(head == NULL){
        head = newnode;
        temp = head;
    } else {
        temp->next=newnode;
        temp=temp->next;
    }
}
// リストを表示する関数
void display(){
    if(head==NULL)
        printf("no node ");
    else{
        temp=head;
        while(temp!=NULL){
            printf("%d ",temp->data);
            temp=temp->next;
        }
    }
}
// 全ノードの積を求める関数
void product_nodes(){
    int product=1;
    temp=head;
    while(temp!=NULL){
        product=product * (temp->data);
        temp=temp->next;
    }
    printf("\nproduct of nodes is : %d" ,product);
}
int main(){
    // リストの作成
    struct node* head = NULL;
    // 要素をリストへ挿入
    insert(1);
    insert(2);
    insert(3);
    insert(4);
    insert(5);
    insert(6);
    // リストの表示
    printf("linked list is : ");
    display();
    // 積を求める関数の呼び出し
    product_nodes();
    return 0;
}

実行結果

linked list is : 1 2 3 4 5 6
product of nodes is : 720

この例では、リストに格納された6つの値 1〜6 をすべて掛け合わせているため、積は 1×2×3×4×5×6 = 720 と出力されます。

計算量と注意点

• 時間計算量: 各ノードを一度ずつ訪問するため O(n) です(nはノード数)。
• 空間計算量: 一時ポインタと積を保持する変数のみで済むため O(1) です。
• オーバーフローへの配慮: ノード数や値が大きい場合、int 型ではすぐに桁あふれが発生します。必要に応じて long long 型などより大きな型を使用しましょう。
• 空リストの扱い: リストが空の場合、初期値 product = 1 がそのまま返るため、要件に応じてエラー処理を追加すると安全です。