Recherchez le nième nœud de la dernière liste chaînée en C++ à l'aide de la méthode récursive

Étant donné une liste à chaînage unique et un entier positif N en entrée. Le but est de trouver le Nème nœud à partir de la fin de la liste donnée en utilisant la récursivité. Si la liste d'entrée a des nœuds a → b → c → d → e → f et N vaut 4, alors le quatrième nœud du dernier sera c.

Nous allons d'abord parcourir jusqu'au dernier nœud de la liste et au retour du nombre d'incréments récursifs (retour en arrière). Lorsque count est égal à N, un pointeur vers le nœud actuel est renvoyé comme résultat.

Voyons différents scénarios d'entrée et de sortie de cette -

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

Sortie− Le Nième nœud à partir du bas Expliquez

comme : 2

− Le troisième nœud est 2.

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

Sortie- Le nœud n'existe pas.

Explication - La liste ne comporte que 7 nœuds, il ne peut donc pas y avoir de 8ème nœud à partir du bas

La méthode utilisée dans le programme ci-dessous est la suivante

Dans cette méthode, nous arriverons d'abord à la fin du. list utilisant la récursion, lors du retour en arrière, nous incrémenterons une variable de comptage statique. Une fois que le nombre est égal à l'entrée N, le pointeur de nœud actuel est renvoyé.

• Prenez une structure Node avec une partie de données int et utilisez Node comme pointeur suivant.

  • Utilise le nœud de structure et la partie de données int. p>

  • La fonction addtohead(Node** head, int data) est utilisée pour ajouter des nœuds à la tête et créer une liste chaînée unidirectionnelle.

  • Utilisez la fonction ci-dessus pour créer une liste chaînée unidirectionnelle avec la tête comme pointeur vers le premier nœud.

  • La fonction affichage (tête Node*) permet d'imprimer la liste chaînée depuis le début

  • Prenez N comme un entier positif.

  • La fonction findNode(Node* head, int n1) récupère le pointeur vers head et n1, et imprime le résultat lorsque le n1ème nœud du dernier est trouvé.

  • Prenez l'explosion comme pointeur vers le n1ème nœud du dernier.

  • Appelez searchNthLast(head, n1, &nlast) pour trouver le nœud.

  • La fonction searchNthLast(Node* head, int n1, Node** nlast) renvoie un pointeur vers le n1ème dernier nœud à partir de la fin de la liste chaînée, la tête étant le premier nœud.

  • Utilisez des variables de nombre statique.

  • Si head est NULL, rien n'est renvoyé.

  • Prenez tmp=head->suivant.

  • Appelez searchNthLast(tmp, n1, nlast) pour parcourir de manière récursive jusqu'au dernier nœud. Après

  • , le compte augmente de 1.

  • Si le nombre devient égal à n1, définissez *nlast=head.

  • Enfin, imprimez la valeur du nœud pointé par nlast comme résultat.

  Exemple

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

  Output

  Si nous exécutons le code ci-dessus, il générera la sortie suivante

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!