让我们首先定义包含数据和指向下一个节点的指针的链表。
struct Node { int data; struct Node* next; };
然后我们创建我们的 createList(Node ** headPtr, int new_data) 函数,它接受一个指向 Node 的 doublePointer 和一个 int 值。在函数内部,我们将新创建的节点下一个指针分配给 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* current 分配给 head 并声明 Node *t。
void deleteNnodesAfterM(Node *head, int M, int N){ Node *current = head, *t; int nodeCount;
在函数内部,我们有一个 while 循环,它在当前不指向 null 时运行。第一个 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;
最后,使用 head 指针的 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<< "原始链表:"<<endl; printList(head); deleteNnodesAfterM(head, M, N); cout<<"删除后的链表:"<<endl; printList(head); return 0; }输出结果
上面的代码将产生以下输出 -
M = 2 N = 2 原始链表: 14 12 10 8 6 4 2 删除后的链表: 14 12 6 4