Delete N Nodes After M Nodes

📋

Delete N Nodes After M Nodes

Edge cases:

</>

IDE

def delete_n_after_m(head: ListNode, M: int, N: int) -> ListNode:public ListNode deleteNAfterM(ListNode head, int M, int N)ListNode* deleteNAfterM(ListNode* head, int M, int N)function deleteNAfterM(head, M, N)

def delete_n_after_m(head, M, N):
    # Write your solution here
    pass

class Solution {
    public ListNode deleteNAfterM(ListNode head, int M, int N) {
        // Write your solution here
        return head;
    }
}

#include <vector>
using namespace std;

ListNode* deleteNAfterM(ListNode* head, int M, int N) {
    // Write your solution here
    return head;
}

function deleteNAfterM(head, M, N) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: List missing nodes that should be keptIncorrect loop boundaries causing deletion of nodes that should be retained.✅ Adjust skip loop to run exactly M times and ensure current pointer is not advanced prematurely.

Wrong: List not deleting nodes when N > 0Deletion loop not executed or pointer not updated after deletion.✅ Add deletion loop that advances temp pointer N times and reconnect current.next to temp.

Wrong: Function crashes or infinite loops on empty listNo null checks before accessing node pointers.✅ Add checks for null head and current pointers before loops.

Wrong: Deletes entire list when M > list lengthDeletion performed even when skip loop ends early due to short list.✅ Return head immediately if skip loop ends before M nodes are skipped.

Wrong: Deletes nodes even when N=0Deletion loop runs regardless of N value.✅ Add condition to skip deletion loop if N=0.

✓

Test Cases

Focus on handling empty and minimal input cases carefully.

Watch out for subtle off-by-one and greedy deletion mistakes.

Optimize your solution to linear time complexity to handle large inputs.

t1_01basic

Input{"head":[1,2,3,4,5,6,7,8,9,10],"M":2,"N":3}

Expected[1,2,6,7,8,9,10]

⏱ Performance - must finish in 2000ms

Keep first 2 nodes (1,2), delete next 3 nodes (3,4,5), keep next 2 nodes (6,7), delete next 3 nodes (8,9,10). Actually, after deleting first 3 nodes after 2, next 2 nodes (6,7) are kept, then next 3 nodes (8,9,10) are deleted. Since only 2 nodes remain after 7, they are kept. So final list is [1,2,6,7,8,9,10].

💡 Traverse the list in segments: keep M nodes, then delete N nodes repeatedly.

💡 Use two loops: one to skip M nodes, another to delete N nodes by adjusting pointers.

💡 After skipping M nodes, set current.next to the node after deleting N nodes to link the list correctly.

Why it failed: Output incorrect - likely failed to correctly skip M nodes or delete N nodes. Fix by ensuring pointer moves exactly M nodes before deletion and reconnect after deleting N nodes.

✓ Correctly implemented the skip M and delete N pattern with proper pointer updates.

t1_02basic

Input{"head":[1,2,3,4,5,6,7,8],"M":3,"N":2}

Expected[1,2,3,6,7,8]

⏱ Performance - must finish in 2000ms

Keep first 3 nodes (1,2,3), delete next 2 nodes (4,5), keep next 3 nodes (6,7,8).

💡 Remember to handle the case when fewer than N nodes remain to delete.

💡 After skipping M nodes, delete up to N nodes or until list ends, then reconnect.

💡 Ensure the last kept node points to the correct next node after deletion.

Why it failed: Incorrect output - likely did not handle partial deletion when fewer than N nodes remain. Fix by checking for null while deleting nodes.

✓ Properly handles partial deletions at list end and reconnects nodes.

t2_01edge

Input{"head":[],"M":2,"N":3}

Expected[]

⏱ Performance - must finish in 2000ms

Empty list input should return empty list.

💡 Check if the head is null before processing.

💡 If list is empty, no nodes to keep or delete.

💡 Return head immediately if null.

Why it failed: Function crashes or returns non-empty for empty input. Fix by adding null check at start.

✓ Correctly returns empty list when input is empty.

t2_02edge

Input{"head":[1],"M":2,"N":3}

Expected[1]

⏱ Performance - must finish in 2000ms

List length less than M means entire list remains unchanged.

💡 When skipping M nodes, if list ends early, return list as is.

💡 No deletion should occur if M nodes can't be skipped.

💡 Check for null during skip loop.

Why it failed: Deletes nodes even when list shorter than M. Fix by stopping skip loop early and returning head.

✓ Correctly retains entire list when length < M.

t2_03edge

Input{"head":[1,2,3,4],"M":2,"N":3}

Expected[1,2]

⏱ Performance - must finish in 2000ms

List length less than M+N means delete only available N nodes after M nodes.

💡 After skipping M nodes, delete up to N nodes or until list ends.

💡 Ensure deletion loop stops if fewer than N nodes remain.

💡 Reconnect last kept node to null if deletion reaches list end.

Why it failed: Fails to delete all available nodes after M or crashes. Fix by checking null in deletion loop.

✓ Correctly deletes all available nodes after M when fewer than N remain.

t2_04edge

Input{"head":[1,2,3,4,5],"M":0,"N":2}

Expected[]

⏱ Performance - must finish in 2000ms

M=0 means delete all nodes immediately, resulting in empty list.

💡 If M=0, no nodes are kept, so entire list should be deleted.

💡 Check for M=0 condition before processing loops.

💡 Return null or empty list if M=0.

Why it failed: Returns non-empty list when M=0. Fix by adding condition to return empty list if M=0.

✓ Correctly returns empty list when M=0.

t3_01corner

Input{"head":[1,2,3,4,5,6,7,8,9],"M":2,"N":2}

Expected[1,2,5,6,9,10]

⏱ Performance - must finish in 2000ms

Tests off-by-one error in skipping and deleting nodes; after skipping 2 nodes, delete 2 nodes, then skip 2 nodes, delete 2 nodes, then skip 1 node. The original list has 9 nodes, but 10 is not present, so corrected expected output includes nodes after deletion: keep nodes 1,2; delete 3,4; keep 5,6; delete 7,8; keep 9. Since 10 does not exist, final list is [1,2,5,6,9].

💡 Carefully count nodes when skipping and deleting to avoid off-by-one errors.

💡 Ensure loops run exactly M and N times or until list ends.

💡 Update current pointer correctly after deletion to continue pattern.

Why it failed: Output too many or too few nodes due to off-by-one in loops. Fix by adjusting loop ranges to run from 1 to M and 1 to N exactly.

✓ Correctly handles exact M and N node counts without off-by-one errors.

t3_02corner

Input{"head":[1,2,3,4,5,6,7,8,9,10],"M":3,"N":0}

Expected[1,2,3,4,5,6,7,8,9,10]

⏱ Performance - must finish in 2000ms

N=0 means no nodes are deleted; list remains unchanged.

💡 If N=0, skip deletion step entirely.

💡 Check for N=0 condition before deletion loop.

💡 Return original list if no deletion required.

Why it failed: Deletes nodes even when N=0. Fix by skipping deletion loop if N=0.

✓ Correctly returns original list when N=0.

t3_03corner

Input{"head":[1,2,3,4,5,6,7,8,9,10],"M":1,"N":1}

Expected[1,3,5,7,9]

⏱ Performance - must finish in 2000ms

Tests greedy trap: deleting nodes one by one without proper pointer update can cause skipping nodes incorrectly.

💡 Avoid deleting nodes one at a time without reconnecting the list properly.

💡 Use pointer to jump over N nodes at once after skipping M nodes.

💡 Update current.next to the node after N deletions to maintain list integrity.

Why it failed: Incorrect output due to deleting nodes one by one and losing track of next node. Fix by deleting N nodes in a loop and reconnecting current.next to the node after deletions.

✓ Properly deletes N nodes after M nodes with correct pointer updates.

t4_01performance

Input{"head":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"M":50000,"N":50000}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 nodes, M=50000, N=50000 to test O(n) time complexity within 2 seconds. (Reduced from 100000 to 100 for input validity and executor parsing.)

💡 Algorithm must run in linear time O(n) to pass performance test.

💡 Avoid nested loops or recursion that cause O(n^2) or worse.

💡 Use iterative pointer manipulation to skip and delete nodes efficiently.

Why it failed: TLE due to inefficient nested loops or recursion. Fix by implementing single pass iterative solution with O(n) complexity.

✓ Algorithm runs in O(n) time and passes performance constraints.

Practice

1. You are given an array of n + 1 integers where each integer is between 1 and n (inclusive). There is exactly one duplicate number but it could be repeated multiple times. Which approach guarantees finding the duplicate in O(n) time and O(1) space without modifying the input array?

easy

A. Sort the array and then scan for consecutive duplicates

B. Use two pointers moving at different speeds to detect a cycle in the array values

C. Use a hash set to track seen numbers and return the first duplicate

D. Use nested loops to compare every pair of elements

Solution

1. Step 1: Understand the problem constraints

   The array contains n+1 integers with values from 1 to n, guaranteeing at least one duplicate. The input cannot be modified and extra space must be O(1).

2. Step 2: Identify the approach that fits constraints

   Sorting modifies the array, hash sets use extra space, nested loops are O(n²). Floyd's cycle detection uses two pointers at different speeds to find a cycle in O(n) time and O(1) space without modifying the array.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two-pointer cycle detection fits all constraints [OK]

Hint: Cycle detection fits O(n) time and O(1) space [OK]

Common Mistakes:

• Assuming sorting is allowed despite input constraints
• Believing hash sets use constant space
• Thinking nested loops are efficient enough

2. You are given a problem where you repeatedly transform a number by replacing it with the sum of the squares of its digits. The goal is to determine if this process eventually reaches 1 or falls into a repeating cycle. Which algorithmic approach is best suited to efficiently detect cycles in this implicit sequence without extra space?

easy

A. Dynamic Programming with memoization to store intermediate results

B. Breadth-First Search (BFS) to explore all possible transformations

C. Greedy approach to pick the next number with the smallest digit sum

D. Floyd's Cycle Detection (Fast and Slow Pointers) to detect cycles in sequences

Solution

1. Step 1: Understand the problem as detecting cycles in a sequence generated by a function

   The problem involves repeatedly applying a function to a number to generate a sequence. Detecting if this sequence reaches 1 or cycles indefinitely is a classic cycle detection problem.

2. Step 2: Identify Floyd's Cycle Detection as the optimal approach

   Floyd's fast and slow pointers efficiently detect cycles in sequences without extra space, unlike DP or BFS which require additional memory or are not suited for implicit sequences.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cycle detection in implicit sequences -> Floyd's algorithm [OK]

Hint: Cycle detection in sequences -> Floyd's fast-slow pointers [OK]

Common Mistakes:

• Confusing cycle detection with DP or BFS approaches

3. Given the following code for checking if a linked list is a palindrome, what is the final return value when the input list is 1 -> 2 -> 1?

easy

A. Infinite loop

B. False

C. True

D. Raises an exception due to null pointer

Solution

1. Step 1: Trace fast and slow pointers

   For list 1 -> 2 -> 1, slow ends at node with value 2, fast reaches end.

2. Step 2: Reverse second half and compare

   Second half starting at 2 -> 1 is reversed to 1 -> 2. Compare nodes: 1==1, 2==2, all match, so return True.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Palindrome list returns True after correct reversal and comparison [OK]

Hint: Check pointer movement and reversed half comparison carefully [OK]

Common Mistakes:

• Misplacing slow pointer causing wrong half reversal
• Off-by-one error in comparison loop
• Forgetting to advance second_half_start pointer

4. You are given a singly linked list and asked to reorder it so that the nodes are arranged in the order: first node, last node, second node, second last node, and so on. Which approach guarantees an optimal in-place solution with O(n) time and O(1) extra space?

easy

A. Use a brute force approach by storing all nodes in an array and then rearranging pointers.

B. Use dynamic programming to store intermediate reorder states and build the final list.

C. Recursively reorder the list by traversing to the end and merging nodes from both ends.

D. Find the middle of the list using fast and slow pointers, reverse the second half, then merge the two halves.

Solution

1. Step 1: Identify the problem constraints

   The problem requires reordering the list in-place with O(n) time and O(1) space.

2. Step 2: Evaluate approaches

   Brute force uses extra space, recursion uses O(n) stack space, and DP is not applicable here. The fast-slow pointer approach finds the middle, reverses the second half, and merges in-place efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Fast-slow pointer approach is classic for in-place reorder [OK]

Hint: Fast-slow pointer + reverse + merge is classic in-place reorder [OK]

Common Mistakes:

• Thinking recursion is O(1) space
• Using DP for linked list reorder
• Assuming array storage is in-place

5. Consider the following code snippet for palindrome check. Which line contains a subtle bug that can cause incorrect results on odd-length lists?

medium

A. Line where second_half_start is assigned by reversing slow

B. Line where slow pointer is advanced in the while loop

C. Line where first_half_start and second_half_start values are compared

D. Line where fast pointer is advanced in the while loop

Solution

1. Step 1: Understand midpoint selection

   For odd-length lists, slow points to the middle node, which should be skipped before reversal.

2. Step 2: Identify bug in reversal start

   Reversing from slow includes the middle node, causing mismatch in comparison.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct approach skips middle node before reversal on odd-length lists [OK]

Hint: Check if middle node is excluded before reversing second half [OK]

Common Mistakes:

• Reversing from slow without skipping middle node
• Incorrect fast/slow pointer advancement
• Not handling odd-length lists separately