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

出力 −ノードが存在しません。

説明 −リストには7つのノードしかないため、最後から8番目のノードはありません。

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

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

• intデータ部分とノードを次のポインタとして持つ構造体ノードを取ります。

• 関数addtohead（Node ** head、int data）は、ノードをヘッドに追加して、単一リンクリストを作成するために使用されます。

• 上記の関数を使用して、最初のノードへのポインタとしてheadを使用して、単一リンクリストを作成します。

• 関数display（Node * head）は、ヘッドノードから始まるリンクリストを印刷するために使用されます。

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

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

• 最後からn番目のノードへのポインタとして爆風を取ります。

• searchNthLast（head、n1、＆nlast）を呼び出して、そのノードを見つけます。

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

• 静的カウント変数を取得します。

• 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