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

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

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

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

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

Salin selepas log masuk

KESIMPULAN

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!