C++での再帰的な挿入とトラバーサルのリンクリスト

リンクリストを形成するために使用される整数値が与えられます。タスクは、最初に挿入し、次に再帰的アプローチを使用して単一リンクリストをトラバースすることです。

最後にノードを再帰的に追加

• ヘッドがNULLの場合→ヘッドにノードを追加

• それ以外の場合は、headに追加します（head→next）

ノードの再帰的走査

• ヘッドがNULLの場合→終了

• それ以外の場合はprint（head→next）

例

入力 − 1 --2 -7 -9 -10

出力 −リンクリスト：1→2→7→9→10→NULL

入力 − 12-21-17-94-18

出力 −リンクリスト：12→21→17→94→18→NULL

以下のプログラムで使用されているアプローチは次のとおりです

このアプローチでは、関数を使用してノードを追加し、単一リンクリストをトラバースして、次の入力のためにそれらを再帰的に呼び出します。

• 整数と次のポインタSLLNode*を含む構造SLLNodeを次に取ります。

• 関数addtoEnd（SLLNode * head、int data）は、リストのヘッドへのポインターとデータ部分の整数を取り、リンクリストの最後にノードを追加します。

• ヘッドポインタがNULLの場合、リストは空です。新しいノードを追加して、ヘッドとして設定します。ヘッド→ネクストをNULLとして追加します。このノードへのポインタを返します

• headがnullでない場合は、head-> next =addtoEnd（head-> next、data）を使用してノードをhead→nextに追加します。

• 関数traverseList（SLLNode * head）は、headからトラバースを開始し、各値を出力します。

• ヘッドがNULLの場合は、NULLを出力して戻ります。

• それ以外の場合は、データ値を出力し、traverseList（head-> next）を使用して次にトラバースします。

• addtoEnd（）を使用してメインのリストを作成し、traverseList（）を使用してリストを出力します。

例

#include <bits/stdc++.h>
using namespace std;
struct SLLNode {
   int data;
   SLLNode* next;
};
SLLNode* addtoEnd(SLLNode* head, int data){
   if (head == NULL){
      SLLNode *nodex = new SLLNode;
      nodex->data = data;
      nodex->next = NULL;
      return nodex;
   }
   else{
      head->next = addtoEnd(head->next, data);
    }
   return head;
}
void traverseList(SLLNode* head){
   if (head == NULL){
      cout <<"NULL";
      return;
   }
   cout << head->data << " -> ";
   traverseList(head->next);
}
int main(){
   SLLNode* head1 = NULL;
   head1 = addtoEnd(head1, 1);
   head1 = addtoEnd(head1, 8);
   head1 = addtoEnd(head1, 56);
   head1 = addtoEnd(head1, 12);
   head1 = addtoEnd(head1, 34);
   cout<<"Linked List is :"<<endl;
   traverseList(head1);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます

Linked List is :
1 -> 8 -> 56 -> 12 -> 34 -> NULL