Suchen Sie mithilfe der rekursiven Methode den n-ten Knoten aus der letzten verknüpften Liste in C++

Gegeben sei eine einfach verknüpfte Liste und eine positive ganze Zahl N als Eingabe. Das Ziel besteht darin, mithilfe der Rekursion den N-ten Knoten am Ende der angegebenen Liste zu finden. Wenn die Eingabeliste Knoten a → b → c → d → e → f hat und N 4 ist, dann ist der vierte Knoten vom letzten c.

Wir werden zuerst bis zum letzten Knoten in der Liste durchlaufen und bei der Rückkehr von der rekursiven (Backtracking) Inkrementzählung. Wenn count gleich N ist, wird als Ergebnis ein Zeiger auf den aktuellen Knoten zurückgegeben.

Sehen wir uns verschiedene Eingabe- und Ausgabeszenarien dieser -

Eingabe- Liste an: - 1 → 5 → 7 → 12 → 2 → 96 → 33 N=3

Ausgabe− Der N-te Knoten von unten Erklären Sie

als: 2

− Der dritte Knoten ist 2.

Eingabe− Liste: - 12 → 53 → 8 → 19 → 20 →96 → 33 N=8 p>

Ausgabe- Knoten existiert nicht.

Erklärung - Die Liste hat nur 7 Knoten, daher kann es keinen 8. Knoten von unten geben.

Die im Programm unten verwendete Methode ist wie folgt:

Bei dieser Methode erreichen wir zuerst das Ende Liste mithilfe von Rekursion. Während des Backtrackings erhöhen wir eine statische Zählvariable. Sobald count gleich der Eingabe N ist, wird der aktuelle Knotenzeiger zurückgegeben.

• Nehmen Sie einen Strukturknoten mit einem int-Datenteil und verwenden Sie Knoten als nächsten Zeiger.

  • Verwendet die Struktur Node und den Int-Datenteil. p>

  • Die Funktion addtohead(Node** head, int data) wird verwendet, um Knoten zum Kopf hinzuzufügen und eine einseitig verknüpfte Liste zu erstellen.

  • Verwenden Sie die obige Funktion, um eine einseitig verknüpfte Liste mit dem Kopf als Zeiger auf den ersten Knoten zu erstellen.

  • Die Funktion display(Node* head) wird verwendet, um die verknüpfte Liste von Anfang an zu drucken.

  • Nehmen Sie N als positive Ganzzahl.

  • Die Funktion findNode(Node* head, int n1) ruft den Zeiger auf head und n1 ab und gibt das Ergebnis aus, wenn der n1. Knoten von unten gefunden wird.

  • Nehmen Sie Blast als Zeiger auf den 1. Knoten vom letzten.

  • Rufen Sie searchNthLast(head, n1, &nlast) auf, um den Knoten zu finden.

  • Funktion searchNthLast(Node* head, int n1, Node** nlast) gibt einen Zeiger auf den n1-letzten Knoten vom Ende in der verknüpften Liste zurück, wobei der Kopf der erste Knoten ist.

  • Verwenden Sie statische Zählvariablen.

  • Wenn head NULL ist, wird nichts zurückgegeben.

  • Nehmen Sie tmp=head->next.

  • Rufen Sie searchNthLast(tmp, n1, nlast) auf, um rekursiv bis zum letzten Knoten zu durchlaufen. Nach

  • erhöht sich die Anzahl um 1.

  • Wenn count gleich n1 wird, dann setzen Sie *nlast=head.

  • Zum Schluss wird der Wert des Knotens, auf den nlast zeigt, als Ergebnis ausgegeben.

  Beispiel

  #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;
  }

  Ausgabe

  Wenn wir den obigen Code ausführen, wird die folgende Ausgabe generiert

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

Das obige ist der detaillierte Inhalt vonSuchen Sie mithilfe der rekursiven Methode den n-ten Knoten aus der letzten verknüpften Liste in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!