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.
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);
}
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;
}