C++のリンクリストの代替ノードの合計

この問題では、リンクリストが表示されます。私たちのタスクは、リンクリストの代替ノードの合計を出力することです。

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

では、問題に戻りましょう。ここでは、リンクリストの代替ノードを追加します。これは、ノードが位置0、2、4、6、…

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

入力

4 → 12 → 10 → 76 → 9 → 26 → 1

出力

24

説明

considering alternate strings −
4 + 10 + 9 + 1 = 24

この問題を解決するために、各ノードを1つずつ、すべてのネストノードにアクセスします。合計に付加価値を付けます。ノードをチェックし続けるために、フラグを使用します。

これは、反復または再帰を使用して実行できます。ここで両方について説明します

例

反復的なアプローチ

#include <iostream>
using namespace std;
struct Node {
   int data;
   struct Node* next;
};
void pushNode(struct Node** head_ref, int newData) {
   struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
   newNode->data = newData;
   newNode->next = (*head_ref);
   (*head_ref) = newNode;
}
int sumAlternateNodeIt(struct Node* head) {
   bool flag = true;
   int sum = 0;
   while (head != NULL){
      if (flag)
         sum += head->data;
      flag = !flag;
      head = head->next;
   }
   return sum;
}
int main(){
   struct Node* head = NULL;
   pushNode(&head, 54);
   pushNode(&head, 12);
   pushNode(&head, 87);
   pushNode(&head, 1);
   pushNode(&head, 99);
   pushNode(&head, 11);
   cout<<"The sum of alternate nodes is "<<sumAlternateNodeIt(head);
   return 0;
}

出力

The sum of alternate nodes is 24

例

再帰的アプローチ

#include <iostream>
using namespace std;
struct Node {
   int data;
   struct Node* next;
};
void pushNode(struct Node** head_ref, int new_data){
   struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
   new_node->data = new_data;
   new_node->next = (*head_ref);
   (*head_ref) = new_node;
}
void sumAlternateNodeRec(struct Node* node, int& sum, bool flag = true){
   if (node == NULL)
      return;
   if (flag == true)
   sum += (node->data);
   sumAlternateNodeRec(node->next, sum, !flag);
}
int main(){
   struct Node* head = NULL;
   pushNode(&head, 54);
   pushNode(&head, 12);
   pushNode(&head, 87);
   pushNode(&head, 1);
   pushNode(&head, 99);
   pushNode(&head, 11);
   int sum = 0;
   sumAlternateNodeRec(head, sum, true);
   cout<<"The sum of alternate nodes is "<<sum;
   return 0;
}

出力

The sum of alternate nodes is 24