Given a linked list and two integers M and N. Traverse the linked list such that you retain M nodes then delete next N nodes, continue the same till end of the linked list.
Difficulty Level: Rookie
Examples:
Input: M = 2, N = 2 Linked List: 1->2->3->4->5->6->7->8 Output: Linked List: 1->2->5->6 Input: M = 3, N = 2 Linked List: 1->2->3->4->5->6->7->8->9->10 Output: Linked List: 1->2->3->6->7->8 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
The main part of the problem is to maintain proper links between nodes, make sure that all corner cases are handled. Following is C implementation of function skipMdeleteN() that skips M nodes and delete N nodes till end of list. It is assumed that M cannot be 0.
C
// C program to delete N nodes after// M nodes of a linked list#include <stdio.h>#include <stdlib.h>// A linked list nodestruct Node{ int data; struct Node *next;};/* Function to insert a node at the beginning */void push(struct Node ** head_ref, int new_data){ // Allocate node struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); // Put in the data new_node->data = new_data; // Link the old list off the // new node new_node->next = (*head_ref); // Move the head to point to the // new node (*head_ref) = new_node;}// Function to print linked list void printList(struct Node *head){ struct Node *temp = head; while (temp != NULL) { printf("%d ", temp->data); temp = temp->next; } printf("");}// Function to skip M nodes and then // delete N nodes of the linked list.void skipMdeleteN(struct Node *head, int M, int N){ struct Node *curr = head, *t; int count; // The main loop that traverses // through the whole list while (curr) { // Skip M nodes for (count = 1; count<M && curr!= NULL; count++) curr = curr->next; // If we reached end of list, // then return if (curr == NULL) return; // Start from next node and // delete N nodes t = curr->next; for (count = 1; count<=N && t!= NULL; count++) { struct Node *temp = t; t = t->next; free(temp); } // Link the previous list with // remaining nodes curr->next = t; // Set current pointer for next // iteration curr = t; }}// Driver codeint main(){ /* Create following linked list 1->2->3->4->5->6->7->8->9->10 */ struct Node* head = NULL; int M=2, N=3; push(&head, 10); push(&head, 9); push(&head, 8); push(&head, 7); push(&head, 6); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); printf("M = %d, N = %d Given Linked list is :", M, N); printList(head); skipMdeleteN(head, M, N); printf( "Linked list after deletion is :"); printList(head); return 0;} |
Output:
M = 2, N = 3 Given Linked list is : 1 2 3 4 5 6 7 8 9 10 Linked list after deletion is : 1 2 6 7
Time Complexity:
O(n) where n is number of nodes in linked list.
Auxiliary Space: O(1)
Please refer complete article on Delete N nodes after M nodes of a linked list for more details!
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
