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