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. Given the following code, what is the output when calling nth_from_end(head, 3) where head is a linked list with values [5, 10, 15, 20]?

easy

A. 5

B. 15

C. 20

D. 10

Solution

1. Step 1: Trace stack contents after traversal

   Stack after pushing nodes: [5, 10, 15, 20]

2. Step 2: Pop n-1=2 times and then pop once more for value

   Pop 1: 20, Pop 2: 15, final pop returns 10 which is the 3rd from end

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   3rd from end in [5,10,15,20] is 10 [OK]

Hint: Stack top is last node; pop n times to get nth from end [OK]

Common Mistakes:

• Off-by-one popping
• Returning node instead of value
• Confusing index from front vs end

3. You are given a singly linked list and need to determine if it reads the same forwards and backwards. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Use fast and slow pointers to find the middle, reverse the second half in-place, then compare both halves.

B. Convert the linked list to an array and check palindrome by comparing elements from both ends.

C. Use a hash set to store visited nodes and check for palindrome by comparing values.

D. Use a recursive approach to compare nodes from start and end simultaneously.

Solution

1. Step 1: Identify the problem constraints

   The problem requires checking palindrome in O(n) time and O(1) space.

2. Step 2: Evaluate approaches

   Converting to array uses O(n) space, recursion uses O(n) stack space, and hash set is not suitable for palindrome check. Using fast and slow pointers to reverse second half in-place meets both time and space requirements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Optimal approach uses fast-slow pointers and in-place reversal [OK]

Hint: Optimal palindrome check uses fast-slow pointers and in-place reversal [OK]

Common Mistakes:

• Assuming array conversion is optimal due to simplicity
• Believing recursion uses constant space
• Using hash sets for palindrome detection

4. What is the time and space complexity of the optimal single-pass two-pointer approach to find the middle node of a singly linked list with n nodes?

medium

A. Time: O(n), Space: O(1)

B. Time: O(n^2), Space: O(1)

C. Time: O(n), Space: O(n)

D. Time: O(log n), Space: O(1)

Solution

1. Step 1: Identify time complexity

   Fast pointer moves two steps per iteration, slow moves one; total iterations proportional to n -> O(n) time.

2. Step 2: Identify space complexity

   Only two pointers used, no extra data structures -> O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time and constant space for two-pointer traversal [OK]

Hint: Two pointers traverse list once, no extra storage [OK]

Common Mistakes:

• Confusing space with O(n) due to recursion
• Assuming nested loops cause O(n^2)
• Thinking fast pointer halves complexity to O(log n)

5. Suppose the array can contain multiple duplicates and some numbers appear more than twice. Which modification to Floyd's cycle detection algorithm correctly finds any duplicate number?

hard

A. No modification needed; Floyd's algorithm works regardless of duplicate count

B. Use a hash set to track visited numbers instead of cycle detection

C. Run Floyd's algorithm multiple times, removing found duplicates each time

D. Floyd's algorithm still works because the cycle corresponds to any duplicate, even if repeated

Solution

1. Step 1: Understand Floyd's algorithm behavior with multiple duplicates

   The cycle in the array corresponds to the repeated number's indices. Even if duplicates appear multiple times, the cycle exists and Floyd's algorithm detects its entrance.

2. Step 2: Confirm no need for multiple runs or extra data structures

   Floyd's algorithm finds one duplicate per run. It does not require modification to detect duplicates repeated more than twice.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cycle detection finds the cycle entrance regardless of duplicate frequency [OK]

Hint: Cycle entrance corresponds to duplicate regardless of count [OK]

Common Mistakes:

• Assuming Floyd's algorithm only works if duplicate appears twice
• Thinking multiple runs or extra space are needed
• Confusing cycle detection with hash-based methods