Remove every k | C ++ program to delete every k - th Node of a singly linked list . ; Linked list Node ; To remove complete list ( Needed forcase when k is 1 ) ; Deletes every k - th node and returns head of modified list . ; If linked list is empty ; Initialize ptr and prev before starting traversal . ; Traverse list and delete every k - th node ; increment Node count ; check if count is equal to k if yes , then delete current Node ; put the next of current Node in the next of previous Node ; set count = 0 to reach further k - th Node ; update prev if count is not 0 ; Function to print linked list ; Utility function to create a new node . ; Driver program to test count function ; Start with the empty list
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * next ; } ; void freeList ( Node * node ) { while ( node != NULL ) { Node * next = node -> next ; delete ( node ) ; node = next ; } } Node * deleteKthNode ( struct Node * head , int k ) { if ( head == NULL ) return NULL ; if ( k == 1 ) { freeList ( head ) ; return NULL ; } struct Node * ptr = head , * prev = NULL ; int count = 0 ; while ( ptr != NULL ) { count ++ ; if ( k == count ) { delete ( prev -> next ) ; prev -> next = ptr -> next ; count = 0 ; } if ( count != 0 ) prev = ptr ; ptr = prev -> next ; } return head ; } void displayList ( struct Node * head ) { struct Node * temp = head ; while ( temp != NULL ) { cout << temp -> data << " ▁ " ; temp = temp -> next ; } } struct Node * newNode ( int x ) { Node * temp = new Node ; temp -> data = x ; temp -> next = NULL ; return temp ; } int main ( ) { 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 ; }