Padamkan nod terakhir senarai terpaut menggunakan C++

Kami mempunyai senarai pautan tunggal dan tugas kami ialah memadamkan nod terakhir daripada senarai terpaut ini. Dalam masalah ini, kita hanya perlu melintasi senarai terpaut yang diberikan dan hanya memadamkan nod terakhir.

Kaedah untuk mencari penyelesaian

Dalam kaedah ini kita melintasi senarai pautan yang diberikan dan menjejaki nod sebelumnya dan nod semasa. Apabila nod semasa kami menjadi nod terakhir, kami menukar sebelumnya -> di sebelah NULL dan memadamkan nod semasa.

Contoh

#include <iostream>
using namespace std;

struct Node {
   int data;
   struct Node* next;
};
void push(struct Node** ref, int new_data) { // pushing the node
   struct Node* new_n = new Node;
   new_n->data = new_data;
   new_n->next = (*ref);
   (*ref) = new_n;
}
int main() {
   Node* head = NULL;
   push(&head, 12);
   push(&head, 29);
   push(&head, 11);
   push(&head, 23);
   push(&head, 8);
   auto curr = head, prev = head;
   if (!curr || !curr -> next) // if list only has one element or the list is empty
      cout << "Empty\n";
   else {
      while (curr) { // while curr != NULL
         if (!curr -> next) {
            prev -> next = NULL;
            delete(curr); // freeing the space
            break;
         }
         prev = curr;
         curr = curr -> next; // moving to the next node
      }
   }
   for (Node* temp = head; temp != NULL; temp = temp->next) // printing the data
      cout << temp->data << " ";

   return 0;
}

Output

8 23 11 29

Penjelasan kod di atas

Dalam kaedah ini, kami melelar melalui tatasusunan, menjejaki nod semasa dan nod sebelumnya. Apabila nod semasa menjadi nod terakhir, kami menukar sebelumnya -> di sebelah NULL dan memadamkan nod semasa. Kerumitan masa keseluruhan program yang diberikan ialah O(N), di mana N ialah saiz senarai yang diberikan.

Kerumitan Masa - O(N)

N: saiz tatasusunan yang diberikan

Kesimpulan

Dalam artikel ini, kami menyelesaikan masalah mengalih keluar nod terakhir daripada senarai terpaut yang diberikan. Kami juga mempelajari program C++ untuk masalah ini dan pendekatan lengkap kami untuk menyelesaikannya. Kita boleh menulis program yang sama dalam bahasa lain seperti C, Java, Python dan bahasa lain. Semoga artikel ini membantu anda.

Atas ialah kandungan terperinci Padamkan nod terakhir senarai terpaut menggunakan C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!