Delete every Kth node from circular linked list | C ++ program to delete every kth Node from circular linked list . ; structure for a Node ; Utility function to print the circular linked list ; Function to delete every kth Node ; If list is empty , simply return . ; take two pointers - current and previous ; Check if Node is the only Node \ If yes , we reached the goal , therefore return . ; Print intermediate list . ; If more than one Node present in the list , Make previous pointer point to current Iterate current pointer k times , i . e . current Node is to be deleted . ; If Node to be deleted is head ; If Node to be deleted is last Node . ; Function to insert a Node at the end of a Circular linked list ; Create a new Node ; if the list is empty , make the new Node head Also , it will point to itself . ; traverse the list to reach the last Node and insert the Node ; Driver program to test above functions ; insert Nodes in the circular linked list ; Delete every kth Node from the circular linked list .
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; Node * next ; Node ( int x ) { data = x ; next = NULL ; } } ; void printList ( Node * head ) { if ( head == NULL ) return ; Node * temp = head ; do { cout << temp -> data << " - > " ; temp = temp -> next ; } while ( temp != head ) ; cout << head -> data << endl ; } void deleteK ( Node * * head_ref , int k ) { Node * head = * head_ref ; if ( head == NULL ) return ; Node * curr = head , * prev ; while ( true ) { if ( curr -> next == head && curr == head ) break ; printList ( head ) ; for ( int i = 0 ; i < k ; i ++ ) { prev = curr ; curr = curr -> next ; } if ( curr == head ) { prev = head ; while ( prev -> next != head ) prev = prev -> next ; head = curr -> next ; prev -> next = head ; * head_ref = head ; free ( curr ) ; } else if ( curr -> next == head ) { prev -> next = head ; free ( curr ) ; } else { prev -> next = curr -> next ; free ( curr ) ; } } } void insertNode ( Node * * head_ref , int x ) { Node * head = * head_ref ; Node * temp = new Node ( x ) ; if ( head == NULL ) { temp -> next = temp ; * head_ref = temp ; } else { Node * temp1 = head ; while ( temp1 -> next != head ) temp1 = temp1 -> next ; temp1 -> next = temp ; temp -> next = head ; } } int main ( ) { struct Node * head = NULL ; insertNode ( & head , 1 ) ; insertNode ( & head , 2 ) ; insertNode ( & head , 3 ) ; insertNode ( & head , 4 ) ; insertNode ( & head , 5 ) ; insertNode ( & head , 6 ) ; insertNode ( & head , 7 ) ; insertNode ( & head , 8 ) ; insertNode ( & head , 9 ) ; int k = 4 ; deleteK ( & head , k ) ; return 0 ; }