Delete Nodes On Regular Intervals

Ninja
0/200
Average time to solve is 20m
profile
Contributed by
7 upvotes
Asked in company
Razorpay

Problem statement

You are given two integers, ‘A’ and ‘B’, and the ‘head’ of a linked list. You are also given ‘N’, denoting the number of nodes in the linked list. You have to return the head of the modified, linked list by removing the nodes in the following way:

  • Start with the head as the current node.
  • Starting with the current node, keep the first ‘A’ nodes.
  • Remove the next ‘B’ nodes.
  • Repeat steps 2 and 3 until we have reached the end of the node.
Example: 
Input: ‘A’ = 2, ‘B’ = 2, ‘N’ = 8, ‘head’ = [1, 2, 3, 4, 5, 6, 7, 8]

Output: [1, 2, 5, 6]

Explanation: Keep the first A(2) nodes, delete the next B(2) nodes, and continue until we have reached the end of the linked list.
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
First-line contains 'T', denoting the number of Test cases.

For each Test case:

The first line contains two integers, ‘A’ and ‘B’, denoting the number of nodes to keep and the number of nodes to delete.

The second line contains one integer, ‘N’, denoting the number of nodes in the linked list.

The third line contains N integers denoting the number of nodes in the linked list.
Output format: 
Return the head of the linked list after modifying the linked list as said above.
Note:- 
You don't need to print anything. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 1e3
1 <= A, B <= 100
The value of each node in the linked list is in the range [1 to 1e9]

Time Limit: 1-sec
Sample Input 1:
2
2 2
8
1 2 3 4 5 6 7 8

2 3
4
10 20 30 40
Sample Output 1:
1 2 5 6
10 20
Explanation Of Sample Input 1:
For test case 1:

Input: ‘A’ = 2, ‘B’ = 2, ‘N’ = 8, ‘head’ = [1, 2, 3, 4, 5, 6, 7, 8]

Output: [1, 2, 5, 6]

Explanation: Keep the first A(2) nodes, delete the next B(2) nodes, and continue until we have reached the end of the linked list.


For test case 2:

Input: ‘A’ = 2, ‘B’ = 2, ‘N’ = 8, ‘head’ = [1, 2, 3, 4, 5, 6, 7, 8]

Output: [1, 2, 5, 6]

Explanation: Keep the first A(2) nodes, delete the next B(3) nodes, and continue until we have reached the end of the linked list.

Sample Input 2:
2
10 10
1
8

1 1
4
9 8 7 6
Sample Output 2:
8
9 7
Hint

Use a dummy node to move over ‘A’ nodes, skip ‘B’ nodes and continue until we reach the end of the linked list.

Approaches (1)
Dummy Node Iterative

We will use a dummy node here. A dummy node is a temporary node we create ourselves for easy traversal over the linked list. 

Create a dummy node and point it to the head of the linked list. Now, create a temporary node ‘temp’, which will initially point to the head of the linked list. Each time, move the node ‘temp’, ‘A’ steps forward. After doing this, our node ‘temp’ is at the position from which the next ‘B’ nodes have to be removed. For this, we will shift the ‘temp’ node’s next pointer by ‘B’ nodes. After this, our ‘temp’ node’s next pointer will be pointing to the node from where again, ‘A’ nodes need to be kept in the linked list we keep repeating this process until we reach the end of the linked list.

While traversing over the linked list, we need to ensure that we are not accessing the next node while at the null node (the end of the linked list).
 

The steps are as follows:-

 

// Function to Delete nodes on a regular interval

function deleteNodesOnRegularInterval(int a, int b, ListNode* head):

  1. Create a dummy node ‘dummy’, giving its value as 0.
  2. Point the next pointer of ‘dummy’ to ‘head’.
  3. Create a temporary node ‘temp’ and assign it to ‘dummy’.
  4. While temp != NULL AND temp.next != NULL:
    • Iterate ‘a’ times:
      • If temp == NULL:
        • Break the loop.
      • temp = temp.next
    • Iterate ‘b’ times:
      • If temp == NULL OR temp.next == NULL:
        • Break the loop.
      • temp.next = temp.next.next
  5. Return dummy.next
Time Complexity

O( N ), where N is the number of nodes in the linked list.

 

We are traversing over the linked list one time. 
 

Hence the time complexity is O( N ).

Space Complexity

O( 1 ).

 

We are using only two extra nodes for traversing over the linked list.

 

Hence the space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Delete Nodes On Regular Intervals
Full screen
Console