C++の循環リンクリストのノードの合計

この問題では、循環リンクリストが表示されます。私たちのタスクは、循環リンクリストのノードの合計を見つけるプログラムを作成することです。

リンクリストのすべてのノード値を追加するだけです。

いくつかの重要な定義

• リンクリストは一連のデータ構造であり、リンクを介して相互に接続されています。

• 循環リンクリストは、最初の要素が最後の要素を指し、最後の要素が最初の要素を指すリンクリストのバリエーションです。単一リンクリストと二重リンクリストの両方を循環リンクリストにすることができます。

では、問題を理解するために例を見てみましょう。

入力

14 -> 1 -> 7 -> 9 -> 2 -> 6

出力

39

説明

sum = 14 + 1 + 7 + 9 + 2 + 6 = 39

この問題を解決するために、リンクリストをトラバースします。そして、各ノードの値を合計変数に追加します。次に、リスト全体をトラバースしたときに合計を返します。

アルゴリズム

ステップ1 − sum=0およびsumPointer=

ステップ2 − do-while sumPointer！=head。行う

ステップ2.1 −現在のノードの値をsumに追加します。つまり、sum +=sumPointer→value。

ステップ2.2 −次のノードへのポインタをインクリメントします。つまり、sumPointer=sumPointer→next。

ステップ3 −合計を返します。

例

ソリューションを説明するプログラム

#include <iostream>
using namespace std;
struct Node {
   int data;
   struct Node* next;
};
void pushNode(struct Node** head_ref, int data) {
   struct Node* ptr1 = (struct Node*)malloc(sizeof(struct Node));
   struct Node* temp = *head_ref;
   ptr1->data = data;
   ptr1->next = *head_ref;
   if (*head_ref != NULL) {
      while (temp->next != *head_ref)
         temp = temp->next;
         temp->next = ptr1;
   }
   else
      ptr1->next = ptr1;
      *head_ref = ptr1;
}
int CalcSumCirList(struct Node* head) {
   struct Node* sumPointer = head;
   int sum = 0;
   if (head != NULL) {
      do {
         sumPointer = sumPointer->next;
         sum += sumPointer->data;
      }
       while (sumPointer != head);
   }
   return sum;
}
int main(){
   struct Node* head = NULL;
   pushNode(&head, 4);
   pushNode(&head, 7);
   pushNode(&head, 12);
   pushNode(&head, 1);
   pushNode(&head, 9);
   pushNode(&head, 6);
   cout<<"The sum of Circular linked list is "<<CalcSumCirList(head);
   return 0;
}

出力

The sum of Circular linked list is 39