再帰的メソッドを使用して、C++ で最後のリンク リストから n 番目のノードを検索します。

単一リンクリストと入力として正の整数 N を与えます。目標は、再帰を使用して、指定されたリストの末尾から N 番目のノードを見つけることです。入力リストにノード a → b → c → d → e → f があり、N が 4 の場合、最後から 4 番目のノードは c になります。

最初にリスト内の最後のノードまで走査し、再帰的 (バックトラッキング) 増分カウントから戻るときに実行します。 count が N に等しい場合、現在のノードへのポインタが結果として返されます。

このためのさまざまな入出力シナリオを見てみましょう -

入力- リスト: - 1 → 5 → 7 → 12 → 2 → 96 → 33 N= 3

出力- 最後から N 番目のノードは: 2

説明- 3 番目のノードは 2 です。

入力- リスト: - 12 → 53 → 8 → 19 → 20 →96 → 33 N=8 p>

出力- ノードは存在する 。

説明 - リストには 7 つのノードしかないため、下から 8 番目のノードは存在できません。

次のプログラムで使用されるメソッドは次のとおりです

このアプローチでは、最初に再帰を使用してリストの最後に到達し、バックトラック中に静的カウント変数をインクリメントします。 count が入力 N と等しくなると、現在のノード ポインタが返されます。

• int データ部分を持つ構造体 Node を取得し、次のポインターとして Node を使用します。

  • Node 構造と int データ部分を採用します。 p>

  • 関数 addtohead(Node** head, int data) は、head にノードを追加し、一方向リンク リストを作成するために使用されます。

  • 上記の関数を使用して、先頭を最初のノードへのポインターとして、一方向リンク リストを作成します。
  • #関数 display(Node* head) は、リンク リストを先頭から出力するために使用されます。

  • N を正の整数として設定します。

  • 関数 findNode(Node* head, int n1) は、head と n1 へのポインタを取得し、下から n1 番目のノードが見つかったときに結果を出力します。

  • blast を最後から n1 番目のノードへのポインターとして使用します。

  • searchNthLast(head, n1, &nlast) を呼び出してノードを見つけます。

  • 関数 searchNthLast(Node* head, int n1, Node** nlast) は、リンク リストの最後から n1 番目の最後のノードへのポインタを返します。head は最初のノードです。

  • 静的なカウント変数を使用します。

  • head が NULL の場合、何も返されません。
  • tmp=head->next を取得します。

  • searchNthLast(tmp, n1, nlast) を呼び出して、最後のノードまで再帰的に走査します。

  • 次に、カウントに 1 を加えます。

  #count が n1 に等しくなった場合は、*nlast=head を設定します。
  最後に、nlast が指すノードの値を結果として出力します。
  例

  #include <bits/stdc++.h>
  using namespace std;
  struct Node {
     int data;
     Node* next;
  };
  void addtohead(Node** head, int data){
     Node* nodex = new Node;
     nodex->data = data;
     nodex->next = (*head);
     (*head) = nodex;
  }
  void searchNthLast(Node* head, int n1, Node** nlast){
     static int count=0;
     if (head==NULL){
        return;
     }
     Node* tmp=head->next;
     searchNthLast(tmp, n1, nlast);
     count = count + 1;
     if (count == n1){
        *nlast = head;
     }
  }
  void findNode(Node* head, int n1){
     Node* nlast = NULL;
     searchNthLast(head, n1, &nlast);
     if (nlast == NULL){
        cout << "Node does not exists";
     }
     else{
        cout << "Nth Node from the last is: "<< nlast->data;
     }
  }
  void display(Node* head){
     Node* curr = head;
     if (curr != NULL){
        cout<<curr->data<<" ";
        display(curr->next);
     }
  }
  int main(){
     Node* head = NULL;
     addtohead(&head, 20);
     addtohead(&head, 12);
     addtohead(&head, 15);
     addtohead(&head, 8);
     addtohead(&head, 10);
     addtohead(&head, 4);
     addtohead(&head, 5);
     int N = 2;
     cout<<"Linked list is :"<<endl;
     display(head);
     cout<<endl;
     findNode(head, N);
     return 0;
  }

  出力

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

  Linked list is :
  5 4 10 8 15 12 20
  Nth Node from the last is: 12

以上が再帰的メソッドを使用して、C++ で最後のリンク リストから n 番目のノードを検索します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。