Remove Every Kth Node Of The Linked List

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.

You can refer to this link for more information on the linked list.

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’ 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 the 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);
        if (head == NULL)
        {
            head = newNode;
            tail = newNode;
        }
        else
        {
            tail->next = newNode;
            tail = newNode;
        }
        cin >> data;
    }
    return head;
}
// Function used to delete the node
void freeList(Node *node)
{
    while (node != NULL)
    {
        Node *next = node -> next;
        delete(node);
        node = next;
    }
}

Node *getResult(Node *head, int k)
{
    // If linked list has no node
    if (head == NULL)
    {
        return NULL;
    }

    if (k == 1)
    {
        freeList(head);
        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;
    }

    return head;
}

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


int main()
{
    Node *head = takeinput();
    print(head);
    cout << endl;
    int k = 4;
    head = getResult(head, k);

    print(head);
}

You can also try this code with Online C++ Compiler

Run Code

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)

In call to ‘getResult()’, As we are traversing the whole linked list which of the 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).