# Remove Every Kth Node Of The Linked List

Harsh Goyal
Last Updated: May 13, 2022

## Introduction

This blog will discuss the various approaches to solve the Remove every Kth node of the linked list problem. Before jumping into the problem to remove every Kth node of the linked list, let’s first understand a Linked list.

A Linked list is a kind of data structure in which the elements are connected using pointers, and each node has the address of the pointer of its next node.

In this Remove every Kth node of the linked list problem, we need to return the head of the modified linked list after removing all the nodes whose position is the multiple of ‘K’ from the linked list.

For Example:-

List :- 10 -> 15 -> 10 -> 5 -> 145 -> 15 -> 5 -> 11 -> 47 -> 10 -> 15 -> 75, K = 3

Output :- 10 -> 15 -> 5 -> 145 -> 5 -> 11 -> 10 -> 15

## Approach

The Solution considers checking the complete linked list by traversing the whole linked list and deleting every Kth node of the linked list.

Note:- K is always less than or equal to the length of the Linked list.

### Algorithm

Step 1. Create a function ‘getResult()’ that will accept two parameters, i.e., one ‘head’ pointer of the linked list, and the value of ‘K’.

Step 2. Check for the base case with the help of an ‘If’ condition if the value of ‘head’ is ‘null’, then we need to return ‘null’.

Step 3. Check with the help of an ‘If’ condition if the value of ‘K’ is equal to 1, then we need to delete the ‘head’ of the Linked list and return the ‘null’ value.

Step 4. Initialize three variables: ‘temp’ will keep track of the elements of the linked list, ‘previous’ will keep track of the previous node of the ‘temp’, and one variable ‘count’ which will keep track of the count of the ‘temp’.

Step 5. Assign the value of ‘head’ to ‘temp’ and assign the null value to ‘previous’, and ‘count’ with zero.

Step 6. Make an iteration using the ‘while’ loop, which will terminate if the value of ‘temp1’ is null.

Step 7. Increment the ‘count’.

Step 8. Check if the value of ‘count’ is equal to ‘K’, which means it is the ‘Kth’ node that must be deleted.

• If it is the ‘Kth’ node, then assign the value of the ‘next’ pointer of the ‘temp’ node to the ‘next’ pointer of the ‘previous’ node and make the value of ‘count’ equal to zero.

Step 9. If ‘count’ is not equal to zero, then assign the value of ‘temp’ to the ‘previous’ variable and assign the value of the ‘next’ pointer of ‘previous’ to ‘temp’.

Step 10. Return the value of head.

### Implementation in C++

``````#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
int data;
Node *next;
Node(int data)
{
this->data = data;
this->next = NULL;
}
};

Node *takeinput()
{
int data;
cin >> data;
Node *head = NULL, *tail = NULL;
while (data != -1)
{
Node *newNode = new Node(data);
{
tail = newNode;
}
else
{
tail->next = newNode;
tail = newNode;
}
cin >> data;
}
}
// Function used to delete the node
void freeList(Node *node)
{
while (node != NULL)
{
Node *next = node -> next;
delete(node);
node = next;
}
}

{
// If linked list has no node
{
return NULL;
}

if (k == 1)
{
return NULL;
}

Node *temp = head, *previous = NULL;

// Traverse list
int count = 0;
while(temp != NULL)
{
count++;
// If that particular 'temp' node is required Kth node
if (k == count)
{
Node *store = temp -> next;
delete(previous -> next);
previous -> next = store;
count = 0;
}

// update previous if count is not 0
if (count != 0)
{
previous = temp;
}

temp = previous -> next;
}

}

/* Function to print the linked list */
{
while (temp != NULL)
{
cout << temp -> data << " ";
temp = temp -> next;
}
return;
}

int main()
{
cout << endl;
int k = 4;

}
``````

``````Output :

Given Linked List:- 10 -> 15 -> 10 -> 5 -> 145 -> 15 -> 5 -> 11 -> 47 -> 10 -> 15 -> 75
Modified Linked List:- 10 -> 15 -> 10 -> 145 -> 15 -> 5 -> 47 -> 10 -> 15``````

### Complexity Analysis

Time Complexity: O(N)

Incall to ‘getResult()’, As we are traversing the whole linked list which of length ‘N’ only once, therefore, the overall time complexity is O(N).

Space Complexity: O(1)

As we are using constant space, therefore, the overall space complexity will be O(1).

1) What are the types of the Linked list?

2) What is the difference between Singly Linked List and Doubly Linked List?

In Singly Linked List, each node has the address of the pointer to its next node, whereas, in Doubly Linked List, each node has the address of the pointers of its next node and its previous node.

3) What is the Circular Linked List?