删除链表中的每个第K个节点

在本文中，我们将解释如何删除链表中的每个第k个节点。我们必须删除位于k的倍数上的每个节点，即我们必须删除位置为k、2*k、3*k等的节点。

Input : 112->231->31->41->54->63->71->85   k = 3Output : 112->231->41->54->71->85Explanation: As 3 is the k-th node after its deletion list would be :First iteration :112->231->41->54->63->71->85Now we count from 41 the next kth node is 63After the second iteration our list will become : 112->231->41->54->71->85And our iteration continues like this.Input: 14->21->23->54->56->61   k = 1Output: Empty listExplanation: All nodes need to be deleted

登录后复制

在这个问题中，我们将应用一种足够有效的普通方法，因此我们不需要对其进行优化。

寻找解决方案的方法

在此问题中，我们将用计数器遍历链表。如果计数器达到 k，我们删除该节点并刷新计数器以查找当前节点第 k 个位置的下一个元素。

示例

#includeusing 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) {      coutdatanext;   }}// 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  next;            count = 1;         } else {            count++;            prev = curr;            curr = curr -> next;         }      }      displayList(head); // printing the new list   }   return 0;}

登录后复制

输出

20 30 50 60 80

登录后复制

上述方法的时间复杂度为O(N)，其中N是给定链表的大小。

上述代码的解释

在上述方法中，我们首先保留三个东西，第一个是当前指针，第二个是前一个指针，第三个是位置计数器。现在当我们的位置计数器等于k时，我们删除某个节点，调用删除函数并将前一个和当前计数器作为参数传递，然后我们删除当前节点并释放空间，当删除函数完成后，我们将当前指针移动到下一个元素，并将计数器刷新为1，循环此块直到当前指针变为NULL。

结论

在本文中，我们解决了一个问题，即删除链表的每个第k个节点。我们还学习了解决此问题的C++程序和完整的（普通）方法。我们可以使用其他语言（如C、Java、Python和其他语言）编写相同的程序。希望您会发现本文有帮助。

以上就是删除链表中的每个第K个节点的详细内容，更多请关注【创想鸟】其它相关文章！