Remove every Kth node of the Linked list

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

Given a singly linked list and a value K, the task is to remove every Kth node of the linked list.

Problem Statement Understanding

Let’s try to understand the problem statement with help of example.

We have been given a linked list, our task is to remove every Kth node from the linked list.

To understand the question thoroughly, see the given input below. In this input, the given value of K is 2. So, we have to delete every 2nd node of the linked list which are 23, 11, and 6.

Example:

Input:

Output:

Explanation:

I think from the above example the problem statement is clear, so we should now think how we can approach this problem. Try to come up with a approach, it may be bruteforce but before jumping to approach section try to think how will you approach it.

Approach

The idea is to traverse the list from the beginning and if the index of the current node is divisible by K, then delete the current node.

Algorithm

  • Take two pointer variables, current and previous.
  • Initialize the current = head and previous = NULL.
  • If the current node’s index is divisible by K, then delete this node and move current = current→next.
  • If the current node’s index is not divisible by K, then move previous = current and current = current→next.

Dry Run

Code Implementation

#include<stdio.h>
#include<stdlib.h>

struct Node
{
    int data;
    struct Node* next;
};
 
// To remove complete list (Needed for
// case when k is 1)
void freeList(struct Node *node)
{
    while (node != NULL)
    {
        struct Node *next = node->next;
        free(node);
        node  = next;
    }
}
 
// Deletes every k-th node and returns head
// of modified list.
struct Node *deleteKthNode(struct Node *head, int k)
{
    // If linked list is empty
    if (head == NULL)
        return NULL;
 
    if (k == 1)
    {
       freeList(head);
       return NULL;
    }
 
    // Initialize ptr and prev before starting
    // traversal.
    struct Node *ptr = head, *prev = NULL;
 
    // Traverse list and delete every k-th node
    int count = 0;
    while (ptr != NULL)
    {
        // increment Node count
        count++;
 
        // check if count is equal to k
        // if yes, then delete current Node
        if (k == count)
        {
            // put the next of current Node in
            // the next of previous Node
            free(prev->next);
            prev->next = ptr->next;
 
            // set count = 0 to reach further
            // k-th Node
            count = 0;
        }
 
        // update prev if count is not 0
        if (count != 0)
            prev = ptr;
 
        ptr = prev->next;
    }
 
    return head;
}
 
/* Function to print linked list */
void displayList(struct Node *head)
{
    struct Node *temp = head;
    while (temp != NULL)
    {
        printf("%d ",temp->data);
        temp = temp->next;
    }
}
 
// Utility function to create a new node.
struct Node *newNode(int x)
{
    struct Node* temp =
         (struct Node*)malloc(sizeof(struct Node));
    temp->data = x;
    temp->next = NULL;
    return temp;
}
 
/* Driver program to test count function*/
int main()
{
    /* Start with the empty list */
    struct Node* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);
    head->next->next->next->next->next = newNode(6);
    head->next->next->next->next->next->next =
                                        newNode(7);
    head->next->next->next->next->next->next->next =
                                        newNode(8);
    int k = 3;
    head = deleteKthNode(head, k);
 
    displayList(head);
 
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    struct Node* next;
};

Node* deleteKthNode(Node *head,int K)
{
  Node *curr = head, *prv = NULL;
  int index = 1;
  /* Edge case 
  If K = 1 means every node has to be deleted
    that is why we first delete every node and
    then return the empty Linked list as NULL. */
  if(K==1){
      delete head;
      return NULL;
  }
  while(curr!=NULL){
      /* If current node’s index is divisible 
         by K then, delete the current Node.*/
      if(index%K==0){
          Node* temp = curr;
          curr = curr->next;
          prv->next=curr;
          temp->next=NULL;
          delete temp;
      }else{
          prv = curr;
          curr = curr->next;
      }
      index++;
  }
  return head;
}


void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node = new Node;
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

int main()
{

    Node* head = NULL;
    push(&head, 19);
    push(&head, 6);
    push(&head, 15);
    push(&head, 11);
    push(&head, 3);
    push(&head, 23);
    push(&head, 1);
    cout<<"Original Linked List: "<<endl;
    for (Node* temp = head; temp != NULL; temp = temp->next)
        cout << temp->data << " ";
    cout<<endl;
    int K = 2;
    head = deleteKthNode(head,K);
    cout<<"Linked List after removing every Kth node of the original linked list: "<<endl;
    for (Node* temp = head; temp != NULL; temp = temp->next)
        cout << temp->data << " ";
 
    return 0;
}



class KNode
{
    static class Node
    {
	    int data;
	    Node next;
    }
    // To remove complete list (Needed for case when k is 1)
    static Node freeList(Node node)
    {
	    while (node != null)
	    {
		    Node next = node.next;
		    node = next;
	    }
	    return node;
    }
    // Deletes every k-th node and returns head of modified list.
    static Node deleteKthNode(Node head, int k)
    {
	    // If linked list is empty
	    if (head == null)
		    return null;

	    if (k == 1)
	    {
		    head = freeList(head);
		    return null;
	    }
        // Initialize ptr and prev before starting traversal.
	    Node ptr = head, prev = null;

	    // Traverse list and delete every k-th node
	    int count = 0;
	    while (ptr != null)
	    {
		    // increment Node count
		    count++;

		    // check if count is equal to k
		    // if yes, then delete current Node
		    if (k == count)
		    {
			    // put the next of current Node in
			    // the next of previous Node
			    prev.next = ptr.next;

			    // set count = 0 to reach further k-th Node
			    count = 0;
		    }
		    // update prev if count is not 0
		    if (count != 0)
			    prev = ptr;

		    ptr = prev.next;
	    }
	    return head;
    }
    static void displayList(Node head)
    {
	    Node temp = head;
	    while (temp != null)
	    {
		    System.out.print(temp.data + " ");
		    temp = temp.next;
	    }
    }
    static Node newNode(int x)
    {
	    Node temp = new Node();
	    temp.data = x;
	    temp.next = null;
	    return temp;
    }
    public static void main(String args[])
    {
	    /* Start with the empty list */
	    Node head = newNode(1);
	    head.next = newNode(2);
	    head.next.next = newNode(3);
	    head.next.next.next = newNode(4);
	    head.next.next.next.next = newNode(5);
	    head.next.next.next.next.next = newNode(6);

	    int k = 3;
	    head = deleteKthNode(head, k);

	    displayList(head);
    }
}


class Node:
	def __init__(self, data):
		self.data = data
		self.next = None

def freeList(node):
	while (node != None):
		next = node.next
		node = next
	return node

def deleteKthNode(head, k):
	
	if (head == None):
		return None

	if (k == 1):
		freeList(head)
		return None
	
	ptr = head
	prev = None
	count = 0
	while (ptr != None):
		
		count = count + 1

		if (k == count):
			prev.next = ptr.next
			count = 0

		if (count != 0):
			prev = ptr

		ptr = prev.next
	
	return head

def displayList(head):
	temp = head
	while (temp != None):
		print(temp.data, end = ' ')
		temp = temp.next
	
def newNode( x):
	temp = Node(x)
	temp.data = x
	temp.next = None
	return temp

if __name__=='__main__':
	
	head = newNode(1)
	head.next = newNode(23)
	head.next.next = newNode(3)
	head.next.next.next = newNode(11)
	head.next.next.next.next = newNode(15)
	head.next.next.next.next.next = newNode(6)
	head.next.next.next.next.next.next = newNode(9)

	k = 2
	head = deleteKthNode(head, k)

	displayList(head)

Output

Original Linked List:
1 23 3 11 15 6 19
Linked List after removing every Kth node of the original linked list:
1 3 15 19

Time Complexity: O(N), because we have traversed through the linked list once.
[forminator_quiz id=”3978″]

So, In this blog, we have learned how to remove every Kth node of the linked list. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Leave a Reply

Your email address will not be published. Required fields are marked *