Padamkan setiap nod Kth dalam senarai terpaut

Dalam artikel ini, kami akan menerangkan cara memadam setiap nod kth dalam senarai terpaut. Kita perlu memadam setiap nod yang terletak pada gandaan k, iaitu kita perlu memadamkan nod pada kedudukan k, 2*k, 3*k, dsb.

Input : 112->231->31->41->54->63->71->85
   k = 3
Output : 112->231->41->54->71->85
Explanation: As 3 is the k-th node after its deletion list would be :
First iteration :112->231->41->54->63->71->85
Now we count from 41 the next kth node is 63
After the second iteration our list will become : 112->231->41->54->71->85
And our iteration continues like this.

Input: 14->21->23->54->56->61
   k = 1
Output: Empty list
Explanation: All nodes need to be deleted

Dalam masalah ini kami akan menggunakan kaedah remeh yang cukup cekap jadi kami tidak perlu mengoptimumkannya.

Bagaimana untuk mencari penyelesaian

Dalam masalah ini, kami akan melintasi senarai pautan dengan kaunter. Jika pembilang mencapai k, kami memadamkan nod dan menyegarkan pembilang untuk mencari elemen seterusnya pada kedudukan ke-k nod semasa.

Contoh

#include<bits/stdc++.h>
using namespace std;
/* Linked list Node */
struct Node {
   int data;
   struct Node* next;
};
void push(struct Node** ref, int new_data) { // pushing the data into the list

   struct Node* new_n = new Node;
   new_n->data = new_data;
   new_n->next = (*ref);
   (*ref) = new_n;
}
void deletek(Node* prev, Node* curr) { // delete function

   if(prev == NULL) {
      prev = curr;
      curr = curr -> next;
      free(prev);
      prev = NULL;
   } else {
      prev -> next = curr -> next;
      auto tmp = curr;
      free(tmp); // freeing the space
   }
}
/* Function to print linked list */
void displayList(struct Node *head) {
   struct Node *temp = head;
   while (temp != NULL) {
      cout<<temp->data<<" ";
      temp = temp->next;
   }
}
// Function to create a new node.
struct Node *newNode(int x) {
   Node *temp = new Node;
   temp->data = x;
   temp->next = NULL;
   return temp;
}
int main() {
   struct Node* head = NULL;
   push(&head, 80);
   push(&head, 70);
   push(&head, 60);
   push(&head, 50);
   push(&head, 40);
   push(&head, 30);
   push(&head, 20);
   int k = 3; // given k
   Node* curr = head; // current pointer
   Node* prev = NULL; // previous pointer
   int count = 1; // position counter
   if(head == NULL || k == 0) // if list is already empty or k = 0
      cout << "Invalid\n";
   else {
      while(curr) { // traversing the list
         if(count == k) {
            deletek(prev, curr);
            curr = prev -> next;
            count = 1;
         } else {
            count++;
            prev = curr;
            curr = curr -> next;
         }
      }
      displayList(head); // printing the new list
   }
   return 0;
}

Output

20 30 50 60 80

Kerumitan masa kaedah di atas ialah O(N), dengan N ialah saiz senarai terpaut yang diberikan.

Penjelasan kod di atas

Dalam kaedah di atas, kita mula-mula menyimpan tiga perkara, yang pertama ialah penunjuk semasa, yang kedua ialah penunjuk sebelumnya, dan yang ketiga ialah pembilang kedudukan. Sekarang apabila pembilang kedudukan kami sama dengan k, kami memadamkan nod tertentu, memanggil fungsi padam dan lulus pembilang sebelumnya dan semasa sebagai parameter, kemudian kami memadamkan nod semasa dan mengosongkan ruang, apabila fungsi padam selesai, kami bergerak penunjuk semasa Pergi ke elemen seterusnya dan muat semula pembilang kepada 1, gelungkan blok ini sehingga penunjuk semasa menjadi NULL.

Kesimpulan

Dalam artikel ini, kami menyelesaikan masalah memadam setiap nod kth senarai terpaut. Kami juga mempelajari program C++ dan pendekatan lengkap (remeh) untuk menyelesaikan masalah ini. Kita boleh menulis program yang sama dalam bahasa lain seperti C, Java, Python dan lain-lain. Semoga artikel ini membantu anda.

Atas ialah kandungan terperinci Padamkan setiap nod Kth dalam senarai terpaut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!