Cari nod ke-n daripada senarai pautan terakhir dalam C++ menggunakan kaedah rekursif

Diberi senarai terpaut tunggal dan integer positif N sebagai input. Matlamatnya adalah untuk mencari nod N dari penghujung senarai yang diberikan menggunakan rekursi. Jika senarai input mempunyai nod a → b → c → d → e → f dan N ialah 4, maka nod ke-4 dari yang terakhir ialah c.

Kami akan mula-mula merentasi sehingga nod terakhir dalam senarai dan apabila kembali daripada kiraan kenaikan rekursif (backtracking). Apabila kiraan sama dengan N, penunjuk ke nod semasa dikembalikan sebagai hasilnya.

Mari kita lihat pelbagai senario input dan output ini -

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

Keluaran ke bawah Terangkan

sebagai: 2

− Nod ketiga ialah 2.

Input− Senarai: - 12 → 53 → 8 → 19 → 20 →96 → 33 N=8 p>

Output- Nod tidak wujud. . senarai menggunakan rekursi, Semasa menjejak ke belakang kami akan menambah pembolehubah kiraan statik. Setelah kiraan sama dengan input N, penunjuk nod semasa dikembalikan.

Ambil Nod struct dengan bahagian data int dan gunakan Node sebagai penuding seterusnya.

Menggunakan struktur Nod dan bahagian data int. p>

• Fungsi addtohead(nod** head, int data) digunakan untuk menambah nod pada head dan membuat senarai terpaut sehala.
  • Gunakan fungsi di atas untuk mencipta senarai terpaut sehala dengan kepala sebagai penunjuk ke nod pertama.

  • Paparan fungsi(kepala Nod*) digunakan untuk mencetak senarai terpaut dari awal

  • Ambil N sebagai integer positif.

  • Fungsi findNode(nod* kepala, int n1) mendapatkan penuding ke kepala dan n1, dan mencetak hasilnya apabila nod n1 dari yang terakhir ditemui.

  • Ambil letupan sebagai penunjuk ke nod n1 dari yang terakhir.

  • Panggil searchNthLast(kepala, n1, &last) untuk mencari nod.

  • Fungsi searchNthLast(nod* head, int n1, Node** nlast) mengembalikan penuding ke nod terakhir n1 dari penghujung dalam senarai terpaut, dengan kepala menjadi nod pertama.

  • Gunakan pembolehubah kiraan statik.

  • Jika kepala NULL, tiada apa yang dikembalikan.

  • Ambil tmp=head->seterusnya.

  • Panggil searchNthLast(tmp, n1, nlast) untuk melintasi secara rekursif sehingga nod terakhir. Selepas

  • kiraan meningkat sebanyak 1.

  • Jika kiraan menjadi sama dengan n1 maka tetapkan *nlast=kepala.

  • Akhir sekali cetak nilai nod yang ditunjuk oleh nlast sebagai hasilnya.

  • Contoh

    #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

  • Jika kita menjalankan kod di atas, ia akan menghasilkan output berikut

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

Atas ialah kandungan terperinci Cari nod ke-n daripada senarai pautan terakhir dalam C++ menggunakan kaedah rekursif. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!