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.

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’ 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);
        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);
}

 

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).

Frequently asked questions

1) What are the types of the Linked list?

A linked list is of three types:- Singly Linked List, Doubly Linked List, Circular 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?

In Circular Linked List, the tail of the linked list points to the head of the same linked list.

Key takeaways

In this article, we discussed the problem remove every Kth node of the linked list, discussed the various approaches to solving this problem programmatically, the time and space complexities, and how to optimize the approach by reducing the space complexity of the problem. 

 If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information.

Until then, All the best for your future endeavors, and Keep Coding.

 

Was this article helpful ?
0 upvotes