連結リストの交互ノードの積を求めるアルゴリズムとC言語での実装

n個のノードからなる連結リストが与えられたとき、交互（隔番目）のノードの値の積を出力するのが課題です。プログラムはノードの位置を実際に変更することなく、交互ノードの積だけを出力しなければなりません。

例

入力 -: 10 20 30 40 50 60
出力 -: 15000

上記の例では、先頭ノードである10から数えて、交互ノードは「10、30、50」となります。その積は 10 × 30 × 50 = 15000 です。

上図では、先頭ノードから数えた場合の交互ノードが青色で示されており、赤色のノードは計算対象外となります。

アプローチ

• node型の一時ポインタ（例：temp）を用意します。

• このtempポインタを、headポインタが指す先頭ノードに設定します。

• (temp->next != NULL && temp != NULL && temp->next->next != NULL) という条件が成り立つ間、temp を temp->next->next へと2つずつ進めます。

• product = product * (temp->data) として、通過した各交互ノードの値を積算していきます。

アルゴリズム

Start
Step 1 -> ノードの構造体を作成し、temp・next・head を構造体nodeへのポインタとして宣言する
    struct node
        int data
        struct node *next, *head, *temp
    End
Step 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
        End
        Else
            temp = head
            Loop While temp->next != NULL
                temp = temp->next
            End
            newnode->next = NULL
            temp->next = newnode
        End
Step 3 -> リストを表示する関数を宣言する
    void display()
        IF head == NULL
            Print "no node"
        End
        Else
            temp = head
            Loop While temp != NULL
                Print temp->data
                temp = temp->next
            End
        End
Step 4 -> 交互ノードの積を求める関数を宣言する
    void alternate()
        int product を宣言
        temp = head
        product = head->data
        Loop While (temp->next != NULL && temp != NULL && temp->next->next != NULL)
            temp = temp->next->next
            product = product * (temp->data)
        End
        Print product
Step 5 -> main() 内で
    struct node* head = NULL; によりリストを作成
    insert(10) を呼び出してノードを挿入
    display() を呼び出してリストを表示
    alternate() を呼び出して交互ノードの積を求める
Stop

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;
    if(head == NULL) {
        head = newnode;
        head->next = NULL;
    } else {
        temp=head;
        while(temp->next!=NULL) {
            temp=temp->next;
        }
        newnode->next=NULL;
        temp->next=newnode;
    }
}
// リストを表示する関数
void display() {
    if(head==NULL)
        printf("no node ");
    else {
        temp=head;
        while(temp!=NULL) {
            printf("%d ",temp->data);
            temp=temp->next;
        }
    }
}
// 交互要素の積を求める関数
void alternate() {
    int product;
    temp=head;
    product=head->data;
    while(temp->next!=NULL && temp!=NULL && temp->next->next!=NULL) {
        temp=temp->next->next;
        product=product * (temp->data);
    }
    printf("\nproduct of alternate nodes is %d : " ,product);
}
int main() {
    // リストの作成
    struct node* head = NULL;
    // 要素の挿入
    insert(10);
    insert(20);
    insert(30);
    insert(40);
    insert(50);
    insert(60);
    // リストの表示
    printf("linked list is : ");
    display();

    // 交互ノードの積を求める関数の呼び出し
    alternate();
    return 0;
}

実行結果

linked list is : 10 20 30 40 50 60
product of alternate nodes is : 15000

処理のポイント

このアルゴリズムの時間計算量は O(n)、空間計算量は O(1) です。ポインタを2つ先へ進める操作（temp->next->next）によって1つおきにノードを訪問できるため、追加の配列や再帰を使わずに効率的に積を求められます。なお、while文の条件式では NULL 参照を避けるため、必ず「temp->next != NULL」を先に評価する順序が重要です。