Alih keluar pendua daripada senarai terpaut yang diisih menggunakan rekursi

Senarai terpaut ialah jujukan elemen yang disambungkan bersama. Setiap senarai mempunyai pengepala dan satu siri nod, setiap satu daripadanya menyimpan data untuk nod semasa dan memaut ke nod seterusnya. Operasi asas senarai terpaut ialah sisipan, pemadaman, carian dan pemadaman.

Alih keluar pendua daripada senarai terpaut yang diisih

Salah satu cara untuk memadamkan nod ialah menggunakan rekursi. Ideanya adalah untuk membandingkan setiap nod dengan nod jirannya dan mengalih keluar nod pendua di mana ia adalah sama.

Panggilan rekursif kami akan kembali ke nod seterusnya. Jadi untuk elemen seterusnya kita akan panggil fungsi rekursif seperti current_node->next = our_function(node->next).

Kami mempercayai rekursi kami dan nod_arus->seterusnya kini mengandungi senarai terpaut tanpa sebarang unsur pendua.

Dalam kaedah utama kami membida senarai dari awal -

Node* head = new Node(5);
head->next = new Node(5);
head->next->next = new Node(6);
head->next->next->next = new Node(7);
head->next->next->next->next = new Node(7);
head->next->next->next->next->next = new Node(7); 

Algoritma

Proses menggunakan rekursi untuk mengalih keluar pendua daripada senarai terpaut yang diisih adalah seperti berikut.

• Langkah 1 - Buat senarai terpaut dengan semua nilai disusun mengikut urutan

• Langkah 2 - Jika senarai terpaut tidak wujud, program ditamatkan.

• Langkah 3 - Jika senarai terpaut memang wujud, bandingkan nilai seterusnya nod kepala dengan nilai dalam nod kepala. Jika kedua-dua nilai adalah sama, keluarkan pengepala.

• Langkah 4 - Langkah 3 dilaksanakan secara rekursif, #🎜🎜🎜🎜 sebagai kepala list mengalih keluar semua nilai pendua daripada dirinya sendiri.

• Langkah 5 - Output yang diperoleh ialah senarai terpaut yang diisih dengan nilai berbeza

Contoh

Sebagai contoh, kami mempunyai senarai terpaut yang diisih dengan nilai berikut -

1->1->1->2->3->3->4

Mari lihat program C++ yang akan mengalih keluar pendua daripada senarai terpaut yang diisih di atas menggunakan rekursi -

#include <iostream>
using namespace std;
class Node {
   public:
   int data;
   Node* next;
   Node(int data) {
   this->data = data;
   next = NULL;
   }
};
Node* solve(Node* head) {
   if (head == NULL)
   return NULL;
   head->next = solve(head->next);
   if (head->next != NULL && head->next->data == head->data) {
      Node* temp = head->next;
      delete head;
      return temp;
   }
   return head;
}
void printList(Node* node) {
   while (node != NULL) {
      cout << node->data << (node->next == NULL ? "" : "->");
      node = node->next;
   }
}
int main() {
   Node* head = new Node(1);
   head->next = new Node(1);
   head->next->next = new Node(1);
   head->next->next->next = new Node(2);
   head->next->next->next->next = new Node(3);
   head->next->next->next->next->next = new Node(3);
   head->next->next->next->next->next->next = new Node(4);
   cout << "Linked list before: ";
   printList(head);
   head = solve(head);
   cout << "\nLinked list after: ";
   printList(head);
   return 0;
}

Selepas itu, kami menyemak sama ada nod semasa disertakan dalam senarai terpaut. Jika senarai pautan yang memuaskan yang kami perolehi daripada nod semasa -> nod seterusnya mempunyai nilai yang sama dengan nod itu, kami tidak memasukkan nod itu jika tidak, kami memasukkannya.

Nota - Apabila nod semasa adalah NULL, kami mengembalikan keadaan asas rekursi.

Output

Linked list before: 1->1->1->2->3->3->4
Linked list after: 1->2->3->4

KESIMPULAN

Seperti yang kita lihat dengan panggilan rekursif, kami percaya bahawa panggilan seterusnya akan mencapai hasil yang diharapkan daripada masalah yang lain. Kami baru sahaja menyelesaikan submasalah semasa. Dengan mengambil kira perkara ini, kami menyemak sama ada elemen semasa boleh terkandung dan menyerahkan senarai terpaut yang selebihnya kepada panggilan rekursif kami, mempercayainya untuk memberi kami senarai terpaut yang sah dari masa itu. Apabila kami merentasi keseluruhan senarai terpaut, kerumitan masa kaedah kami ialah O(n).

Atas ialah kandungan terperinci Alih keluar pendua daripada senarai terpaut yang diisih menggunakan rekursi. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!