Delete every Kth node in the linked list

In this article, we will explain how to delete every kth node in a linked list. We have to delete every node located on a multiple of k, i.e. we have to delete nodes at positions k, 2*k, 3*k, etc.

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

In this problem we will apply a common method that is efficient enough so we don't need to optimize it.

Methods to find the solution

In this problem, we will traverse the linked list using a counter. If the counter reaches k, we delete the node and refresh the counter to find the next element at the k-th position of the current node.

Example

#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) { // 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) {
      cout<<temp->data<<" ";
      temp = temp->next;
   }
}
// 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 << "Invalid\n";
   else {
      while(curr) { // traversing the list
         if(count == k) {
            deletek(prev, curr);
            curr = prev -> next;
            count = 1;
         } else {
            count++;
            prev = curr;
            curr = curr -> next;
         }
      }
      displayList(head); // printing the new list
   }
   return 0;
}

Output

20 30 50 60 80

The time complexity of the above method is O(N), where N is the size of the given linked list.

Explanation of the above code

In the above method, we first keep three things, the first is the current pointer, the second is the previous pointer, and the third is the position counter. Now when our position counter is equal to k, we delete a certain node, call the delete function and pass the previous and current counter as parameters, then we delete the current node and free up the space, when the delete function completes, we move the current pointer to the next element and refresh the counter to 1, looping this block until the current pointer becomes NULL.

Conclusion

In this article, we solved the problem of deleting every k-th node of a linked list. We also learned a C program and a complete (trivial) method to solve this problem. We can write the same program in other languages ​​like C, Java, Python and others. Hope you find this article helpful.

The above is the detailed content of Delete every Kth node in the linked list. For more information, please follow other related articles on the PHP Chinese website!