Xóa N nút sau M nút của danh sách liên kết trong C ++?

Trước tiên, hãy để chúng tôi xác định danh sách được liên kết chứa dữ liệu và con trỏ đến nút tiếp theo.

struct Node {
   int data;
   struct Node* next;
};

Sau đó, chúng ta tạo hàm createList (Node ** headPtr, int new_data), hàm này nhận một doublePointer cho Node và một giá trị int. Bên trong hàm, chúng ta gán con trỏ tiếp theo của nút mới được tạo cho headptr và sau đó là headptr cho nút mới được tạo.

void createList(Node ** headPtr, int new_data){
   Node* newNode = new Node();
   newNode->data = new_data;
   newNode->next = (*headPtr);
   (*headPtr) = newNode;
}

Phương thức deleteNnodesAfterM (Node * head, int M, int N) lấy nút gốc và các giá trị M và N. Bên trong chúng ta gán Node * hiện tại cho head và cũng khai báo Node * t.

void deleteNnodesAfterM(Node *head, int M, int N){
   Node *current = head, *t;
   int nodeCount;

Bên trong hàm, chúng ta có một vòng lặp while chạy trong khi dòng điện không trỏ đến null. Vòng lặp for đầu tiên chạy cho M lần lặp. Sau khi vòng lặp for đầu tiên kết thúc việc thực thi hiện tại con trỏ trỏ đến nút sau M trong danh sách liên kết. Sau đó, Node * t được gán giá trị current-> next là giá trị đầu tiên bị xóa.

while (current){
   for (nodeCount = 1; nodeCount < M && current!= NULL; nodeCount++)
   current = current->next;
   if (current == NULL)
      return;
   t = current->next;

Vòng lặp for thứ hai chạy trong N lần lặp và giải phóng N số nút khỏi vị trí bắt đầu. Tiếp theo current-> sau đó được gán cho t và t trở thành nút hiện tại của chúng ta.

for (nodeCount = 1; nodeCount<=N && t!= NULL; nodeCount++){
   Node *temp = t;
   t = t->next;
   free(temp);
}
current->next = t;
current = t;

Cuối cùng, printList (Node * head) lấy con trỏ đầu in danh sách được liên kết.

void printList(Node *head){
   Node *temp = head;
   while (temp != NULL){
      cout<<temp->data<<" ";
      temp = temp->next;
   }
   cout<<endl;
}

Ví dụ

Chúng ta hãy xem cách triển khai sau để xóa N nút sau M nút của danh sách được liên kết -

#include <iostream>
using namespace std;
struct Node{
   int data;
   Node *next;
};
void createList(Node ** headPtr, int new_data){
   Node* newNode = new Node();
   newNode->data = new_data;
   newNode->next = (*headPtr);
   (*headPtr) = newNode;
}
void printList(Node *head){
   Node *temp = head;
   while (temp != NULL){
      cout<<temp->data<<" ";
      temp = temp->next;
   }
   cout<<endl;
}
void deleteNnodesAfterM(Node *head, int M, int N){
   Node *current = head, *t;
   int nodeCount;
   while (current){
      for (nodeCount = 1; nodeCount < M && current!= NULL; nodeCount++)
      current = current->next;
      if (current == NULL)
      return;
      t = current->next;
      for (nodeCount = 1; nodeCount<=N && t!= NULL; nodeCount++){
         Node *temp = t;
         t = t->next;
         free(temp);
      }
      current->next = t;
      current = t;
   }
}
int main(){
   Node* head = NULL;
   int M=2, N=2;
   createList(&head, 2);
   createList(&head, 4);
   createList(&head, 6);
   createList(&head, 8);
   createList(&head, 10);
   createList(&head, 12);
   createList(&head, 14);
   cout << "M = " << M<< " N = " << N<<endl;
   cout<< "Original linked list :"<<endl;
   printList(head);
   deleteNnodesAfterM(head, M, N);
   cout<<"Linked list after deletion :"<<endl;
   printList(head);
   return 0;
}

Đầu ra

Đoạn mã trên sẽ tạo ra kết quả sau -

M = 2 N = 2

Original linked list :
14 12 10 8 6 4 2

Linked list after deletion :
14 12 6 4