删除链表中的每个第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 using 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) { coutnext = 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; }登录后复制