删除链表的每个第 K 个节点
在本文中，我们将解释删除链表的每个第k个节点的方法。我们必须删除位于k倍数上的每个节点，即，我们必须删除位于k、2*k、3*k等位置的节点。
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
在这个问题中，我们将应用一种足够有效的常规方法，因此我们不需要对其进行优化。
寻找解决方案的方法
在这个问题中，我们将使用计数器遍历链表。如果计数器命中k，我们删除该节点并刷新计数器以查找当前节点第k个位置的下一个元素。
示例
#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) { //将数据推入列表
struct Node* new_n = new Node;
new_n->data = new_data;
new_n->next = (*ref);
(*ref) = new_n;
}
void deletek(Node* prev, Node* curr) { //删除功能
if(prev == NULL) {
prev = curr;
curr = curr -> next;
free(prev);
prev = NULL;
} else {
prev -> next = curr -> next;
auto tmp = curr;
free(tmp); //释放空间
}
}
/* Function to print linked list */
void displayList(struct Node *head) {
struct Node *temp = head;
while (temp != NULL) {
cout<<temp->data<<" ";
temp = temp->next;
}
}
//创建新节点的函数。
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; //给定k
Node* curr = head; //当前指针
Node* prev = NULL; //前一个指针
int count = 1; //位置计数器
if(head == NULL || k == 0) //如果列表已经为空或k=0
cout << "Invalid\n";
else {
while(curr) { //遍历列表
if(count == k) {
deletek(prev, curr);
curr = prev -> next;
count = 1;
} else {
count++;
prev = curr;
curr = curr -> next;
}
}
displayList(head); //打印新列表
}
return 0;
}输出结果20 30 50 60 80
上述方法的时间复杂度为O(N)，其中N是给定链表的大小。
上面代码的解释
在上面的方法中，我们首先保留三个东西，当前指针，第二个前一个指针，第三个位置计数器。现在，当我们的位置计数器变得等于时，我们删除某个节点知道我们调用函数以使用先前和当前计数器作为参数进行删除，现在我们删除当前节点并在删除功能完成时释放空间现在我们将当前指针移至下一个元素并将我们的计数器刷新为1并循环此块直到我们的当前变为NULL。
结论
在本文中，我们解决了移除链表的每个第k个节点的问题。我们还学习了针对此问题的C++程序以及解决此问题的完整方法(Normal)。我们可以用其他语言编写相同的程序，例如C、java、python和其他语言。我们希望这篇文章对您有所帮助。