데이터와 다음 노드에 대한 포인터를 포함하는 연결 목록을 먼저 정의합시다.
struct Node {
int data;
struct Node* next;
}; 그런 다음 Node와 int 값에 대한 doublePointer를 사용하는 createList(Node ** headPtr, int new_data) 함수를 만듭니다. 함수 내에서 새로 생성된 노드 다음 포인터를 headptr에 할당한 다음 headptr을 새로 생성된 노드에 할당합니다.
void createList(Node ** headPtr, int new_data){
Node* newNode = new Node();
newNode->data = new_data;
newNode->next = (*headPtr);
(*headPtr) = newNode;
} deleteNnodesAfterM(Node *head, int M, int N) 메서드는 루트 노드와 M 및 N 값을 사용합니다. 내부에서 헤드에 현재 Node*를 할당하고 Node *t도 선언합니다.
void deleteNnodesAfterM(Node *head, int M, int N){
Node *current = head, *t;
int nodeCount; 함수 내부에는 현재가 null을 가리키지 않는 동안 실행되는 while 루프가 있습니다. 첫 번째 for 루프는 M 반복 실행됩니다. 첫 번째 for 루프가 현재 실행을 마친 후 포인터는 연결 리스트에서 M 뒤의 노드를 가리킵니다. 그런 다음 노드 *t에는 삭제할 첫 번째 값인 current->next 값이 할당됩니다.
while (current){
for (nodeCount = 1; nodeCount < M && current!= NULL; nodeCount++)
current = current->next;
if (current == NULL)
return;
t = current->next; 두 번째 for 루프는 N 반복 동안 실행되고 시작 위치에서 N 수의 노드를 해제합니다. 그런 다음 current->next가 t에 할당되고 t가 현재 노드가 됩니다.
for (nodeCount = 1; nodeCount<=N && t!= NULL; nodeCount++){
Node *temp = t;
t = t->next;
free(temp);
}
current->next = t;
current = t; 마지막으로 헤드 포인터를 받는 printList(Node *head)는 연결 리스트를 출력합니다.
void printList(Node *head){
Node *temp = head;
while (temp != NULL){
cout<<temp->data<<" ";
temp = temp->next;
}
cout<<endl;
} 예시
연결 리스트의 M개 노드 이후에 N개의 노드를 삭제하는 다음 구현을 살펴보겠습니다. -
#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;
} 출력
위의 코드는 다음 출력을 생성합니다 -
M = 2 N = 2 Original linked list : 14 12 10 8 6 4 2 Linked list after deletion : 14 12 6 4