Wednesday, 8 March 2017

C++ Program to delete every Kth Node of Linked List

This question has been appeared in the interview of the following companies.

Amazon, Mircrosoft

Source: geeksforgeeks 

In the question you to delete the every kth node of the Linked List:
Example:

    If linked list is :   1->2->3->4->5->6->7->8  and k=3
    then output will be: 1->2->4->5->7->8
                       

ALGORITHM

1.   set: count=0
2.   set: current=head  #head node of the linked list
3.   while current!=NULL:
4.           set: count=count+1
5.           If count=k-1:  #evert kth node you have to delete
6.                 if current.next=NULL:
7.                      break
8.                 else:
9.                      current.next=current.next.next
10.                End ifelese
11.                current=current.next
12.                count=0
13.          else:
14.              current=current.next
15.          End IfElse
16.  End While


Program:

#include <stdio.h>
#include <stdlib.h>
struct node
{
    int data;
    struct node *next;
};

class deletekthnode{
    private:
          node* head=NULL,*temp;
          int k;
    public:
          void insert();
          void print();
          node* deletek();

};
void deletekthnode::insert()
{
    

     temp=(struct node*)malloc(sizeof(struct node));
     temp->data=1;
     temp->next=NULL;
     head=temp;
     temp->next=(struct node*)malloc(sizeof(struct node));
     temp=temp->next;
     temp->data=2;
     temp->next=(struct node*)malloc(sizeof(struct node));
     temp=temp->next;
     temp->data=3;
     temp->next=(struct node*)malloc(sizeof(struct node));
     temp=temp->next;
     temp->data=4;
     temp->next=(struct node*)malloc(sizeof(struct node));
     temp=temp->next;
     temp->data=5;
     temp->next=(struct node*)malloc(sizeof(struct node));
     temp=temp->next;
     temp->data=6;
     temp->next=NULL;

        /*calling print function for printing linked list */
        
     print(); 
          
        printf("\n\n");
     /* calling delete function for deleting every kth node*/
     k=3;
     deletek();

     /* calling print function for printing linked list after delete operation */
        printf("\n\n");
     print();

     /*second test case */

     k=2;
     deletek();
        
        printf("\n\n");
     print();

}
node* deletekthnode::deletek()
{
     struct node *current;
     current=head;
     int count=0;
     while(current!=NULL)
     {
            count++;
            if(count==k-1)
            {
                   if(current->next==NULL)
                   {
                          break;
                   }
                   else
                   {
                          current->next=current->next->next;
                   }
                   current=current->next;
                   count=0;
            }
            else
            {
                   current=current->next;
            }
     }
}
void  deletekthnode::print()
{
    struct node *current;
    current=head;
    while(current!=NULL)
    {
              printf("%d ",current->data);
              current=current->next;
    }
}
int main()
{
   deletekthnode dknode;
      dknode.insert();
      return 0;
}


OUTPUT:


EmoticonEmoticon