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.