Repeatedly Delete N nodes after M nodes of a Linked list

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 until end of the linked list.

Input:
M = 2, N = 2
Linked List: 1->2->3->4->5->6->7->8
Output:
Linked List: 1->2->5->6

The main part of the problem is to maintain proper links between nodes, make sure that all corner cases are handled.

Implementation:

typedef struct _Node
{
	int data;
	struct _Node *link;
}Node;

// Function to skip M nodes and then remove N nodes of the linked list.
void SkipAndRemove( node  *head, int M, int N)
{
    node *current = head, *t;
    int count;
 
    while (current)
    {
        // Skip M nodes
        for (count = 1; count<M && current!= NULL; count++)
            current = current->link;
 
        // If we reached end of list, then return
        if (current == NULL)
            return;
 
        // Start from link node and remove N nodes
        t = current->link;
        for (count = 1; count<=N && t!= NULL; count++)
        {
            node *temp = t;
            t = t->link;
            free(temp);
        }
        current->link = t; 
 
        // Set current pointer for link iteration
        current = t;
    }
}

Time Complexity: O(n) where n is number of nodes in linked list.

2 Thoughts on “Repeatedly Delete N nodes after M nodes of a Linked list

  1. praful Pjdurkar on May 24, 2015 at 1:35 am said:

    This will work for java

    public void LinkedListSample() {

    int M =2, N=3;
    LinkedList ll = new LinkedList();
    ll.add(1);
    ll.add(2);ll.add(3);ll.add(4);ll.add(5);ll.add(6);
    ll.add(7);ll.add(8);ll.add(9);ll.add(10);ll.add(11);
    int index = 0;
    while(index<=ll.size()) {
    index += M ;
    System.out.println(index);
    int count = 0;
    while(countll.size()-1) {
    continue;
    }
    else {
    ll.remove(index);
    // index++;
    }

    }
    }
    System.out.println(ll);

    }

  2. Bharath Reddy on April 6, 2016 at 11:18 pm said:

    Java code:
    public ListNode retainMdeleteNnodes(ListNode headNode, int m, int n){
    int size = listLength(headNode);
    if(m == 0){
    System.out.println(“All nodes deleted”);
    return null;
    }else if (n == 0 || size <= m){
    return headNode;
    }
    int retain = 1;
    ListNode retainNode = headNode;
    while(retain < m ){
    retain++;
    retainNode = retainNode.getNext();
    }
    if(size <= m+n){
    retainNode.setNext(null);
    return headNode;
    }
    int deleteCount = 1;
    ListNode deletedNode = retainNode.getNext();
    while(deleteCount < n){
    deleteCount++;
    deletedNode = deletedNode.getNext();
    }
    retainNode.setNext(retainMdeleteNnodes(deletedNode.getNext(),m,n));
    return headNode;
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation