Delete N nodes after M nodes of a linked list

Delete N nodes after M nodes of a linked list

In this problem, we have given a linked list and two integers M and N. We need to traverse the linked list in such a way that we retain M nodes of the linked list and delete N nodes of the linked list continually till the end of the linked list.

Examples:

Input:

M = 3, N = 2

Linked List: 2 ->4 ->6 ->8 ->10 ->12 ->14 ->16

Output:

Linked List: 2 -> 4 -> 6 -> 12 -> 14 -> 16

Input:

M = 1, N = 3

Linked List: 0 -> 12 -> 13 ->4 -> 15 ->6 -> 17 ->8 -> 19

Output:

Linked List: 0 -> 15 -> 19

Input:

M = 1, N = 1

Linked List: 1 ->2 ->3 ->4 ->5 ->6 ->7 ->8 ->9 ->10

Output:

Linked List: 1 ->3 ->5 ->7 ->9

Method:

This method will traverse the given linked list and skip the first m nodes and then delete the next n nodes. It performs this traversing for all the remaining nodes. Here, we need to handle all corner case or boundary conditions and maintain proper links between the nodes of the linked list.

C program to delete N nodes after M nodes of a linked list

 #include<stdio.h>
 #include<stdlib.h>
 // The structure of the node
 struct node
 {
 int info;
 struct node * next;
 };
 struct node * start = NULL;
 // For inserting the elements in the linked list
 void add(int item)
 {
 struct node * t, * p;
 t = (struct node * )malloc( sizeof( struct node ));
 if(start == NULL)
 {
 start = t;
 start -> info = item;
 start -> next = NULL;
 return;
 }
 else
 {
 struct node * p = start;
 while(p -> next != NULL)
 {
 p = p -> next;
 }
 p -> next = t;
 p = p -> next;
 p -> info = item;
 p -> next = NULL;
 }
 }
 // For delete N nodes after M nodes of the linked list
 voidskipMdeleteN(struct node  *head, int M, int N)
 {
 struct node *temp = head, *t;
 int count;
 while (temp)
     {
 for (count = 1; count<M && temp!= NULL; count++)
 temp = temp->next;
 if (temp == NULL)
 return;
          t = temp->next;
 for (count = 1; count<=N && t!= NULL; count++)
         {
 struct Node *temp = t;
             t = t->next;
 free(temp);
         }
 temp->next = t;
 temp = t;
     }
 }
 // To display the elements of the linked list
 void traverse(struct node * t)
 {
 if(t == NULL)
 {
             printf(" Linked list is empty\n");
                                     }
                                     while(t -> next != NULL)
                                     {
                         printf("%d  ->  ", t -> info);
                         t = t -> next;
                         }
                         printf("%d\n", t -> info);
 }
 // Driver Function
 int main()
 {
 int M,N;
 printf("Enter the M and N values:\n");
 scanf("%d%d",&M,&N);
 add(2);
 add(4);
 add(6);
 add(8);
 add(10);
 add(12);
 add(14);
 add(16);
 printf("Linked List before deletion:\n");
 traverse(start);
 skipMdeleteN (start,M,N);
 printf("Linked List after deletion\n");
 traverse(start);
 return 0;
 } 

Output:

Time Complexity: The time complexity of the above method is O(n), where n is the total number of nodes in the linked list.