Problem

Submissions

Hints & solutions

Discuss

Delete N nodes after M nodes of a linked list

Moderate

0/80

Average time to solve is 30m

Contributed by

15 upvotes

Asked in companies

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.

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1 :

3 2 0 -4 -1
1 1

Sample Output 1 :

3 0 -1

Explanation to Sample Input 1 :

The first and third Nodes are retained, and rest are deleted.

Sample Input 2 :

3 2 0 -4 7 -9 -8 10 5 -1
1 2

Sample Output 2 :

3 2 -4 7 -8 10 -1

Explanation to Sample Input 2 :

The first, second, fourth, fifth, seventh and eighth Nodes are retained, and rest are deleted.

Sample Input 3 :

3 2 0 -4 7 -9 -8 10 5 -1
2 1

Sample Output 3 :

3 -4 -8 -1

Explanation to Sample Input 3 :

The first, fourth and seventh Nodes are retained, and rest are deleted.

Hint 1

Try to traverse the linked list doing delete operation in the required manner.

Approaches (1)

Approach 1

Basic Traversal

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.

Time Complexity

O(L), where ‘L’ is the number of nodes in the linked list.

We are just traversing the whole linked list once.

Space Complexity

O(1).

As we are just using a few variables to traverse and delete.

(100% EXP penalty)

Delete N nodes after M nodes of a linked list

Console