Last Updated: 26 Aug, 2020

Delete N nodes after M nodes of a linked list

Moderate

Asked in companies

Solve now

Problem statement

You have given a singly linked list and two integers 'N' and 'M'. Delete 'N' nodes after every 'M' node, or we can say more clearly that traverse the linked list such that you retain 'M' nodes then delete next 'N' nodes, continue the same till the end of the linked list.

Follow Up:

Try to solve this problem in O(N) time complexity and O(1) space complexity.

Input format :

The first line of input contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

The second line contains the two single space-separated integers 'N' and 'M'.

Output format :

For each test case, print a single line containing space-separated integers denoting resultant linked list after performing required operation denoted as the elements separated by a single space and terminated by -1.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints :

0 <= L <= 10 ^ 6
-10 ^ 9 <= DATA <= 10 ^ 9 and DATA != -1
0 <= N <= 10 ^ 6
1 <= M <= 10 ^ 6

Where 'L' is the number of nodes in Linked List and 'N' and 'M' are parameters of the Problem and 'DATA' is the value of any node.

Time Limit: 1 sec.

Solve now

Approaches

01 Approach

We will iterate through the linked list with a variable cur = head while cur != end of the linked list. We will first skip ‘M’ nodes by doing cur = cur -> next ‘M-1’ times.

Now If in between we reached the end of the linked list then we should return the head as we have completed our operation.

Else, now we need to delete next ‘N’ nodes so we can do this by using another variable rem = cur -> next. Delete next ‘N’ nodes using rem while rem!=end of the list.

Now If in between we reached the end of the linked list then we should return the head as we have completed our operation.

Finally, join the previous cur to the next node and update cur:

cur->next = rem

cur = rem

Repeat the above steps until we reach the end of the linked list.

Solve now