Delete N Nodes After M Nodes

▶

Steps

setup

Initialize current pointer at head

Set the 'current' pointer to the head of the list to start processing from the first node.

💡 Starting at head is essential to traverse the entire list sequentially.

Line:

current = head

💡 The algorithm begins traversal from the start of the list.

traverse

Skip first node (M-1 = 1) to reach Mth node

Move 'current' pointer from node 1 to node 2, skipping one node as M=2 means keep first 2 nodes.

💡 Skipping M-1 nodes positions 'current' at the last node to keep before deletion starts.

Line:

for _ in range(1, M):
    if current is null:
        return head
    current = current.next

💡 The 'current' pointer now marks the last node to keep before deletion.

delete

Prepare to delete N nodes after current

Set 'temp' pointer to the node after 'current' (node 3), which is the start of nodes to delete.

💡 We need a separate pointer to traverse and skip the nodes to delete without losing track of the list.

Line:

temp = current.next

💡 'temp' marks the first node to be deleted.

delete

Delete first node (3) by moving temp forward

Move 'temp' pointer from node 3 to node 4, deleting node 3 logically by skipping it.

💡 Moving 'temp' forward simulates deleting nodes by skipping them in the link.

Line:

for _ in range(N):
    if temp is null:
        break
    temp = temp.next

💡 Each move of 'temp' advances the deletion window by one node.

delete

Delete second node (4) by moving temp forward

Move 'temp' pointer from node 4 to node 5, continuing deletion by skipping node 4.

💡 Each step moves 'temp' forward to skip one more node to delete.

Line:

for _ in range(N):
    if temp is null:
        break
    temp = temp.next

💡 Deletion progresses node by node until N nodes are skipped or list ends.

delete

Delete third node (5) by moving temp forward

Move 'temp' pointer from node 5 to node 6, completing deletion of 3 nodes after current.

💡 After moving temp N times, we have identified all nodes to delete.

Line:

for _ in range(N):
    if temp is null:
        break
    temp = temp.next

💡 The deletion window is now fully defined by 'temp' pointer.

connect

Link current node to node after deleted nodes

Set 'current.next' to 'temp' (node 6), skipping over deleted nodes 3,4,5.

💡 This reconnects the list, effectively removing deleted nodes from the chain.

Line:

current.next = temp

💡 Link update is the key operation that removes nodes from the list.

advance

Move current pointer to continue from node 6

Set 'current' to 'temp' (node 6) to repeat the skip-delete process from the new position.

💡 Moving 'current' forward allows the algorithm to process the next segment of the list.

Line:

current = temp

💡 The algorithm processes the list in segments of M kept nodes and N deleted nodes.

traverse

Skip one node to reach Mth node again

Move 'current' from node 6 to node 7, skipping M-1=1 node to position at last node to keep.

💡 Skipping nodes again sets the boundary for the next deletion segment.

Line:

for _ in range(1, M):
    if current is null:
        return head
    current = current.next

💡 The algorithm repeats the skip-delete pattern until the list ends.

delete

Prepare to delete next N nodes after current

Set 'temp' pointer to node 8, the first node to delete after node 7.

💡 Again, 'temp' marks the start of nodes to delete in this segment.

Line:

temp = current.next

💡 The deletion process repeats for the next segment of nodes.

delete

Delete node 8 by moving temp forward

Move 'temp' from node 8 to node 9, marking node 8 for deletion.

💡 Each move of 'temp' skips one node to delete.

Line:

for _ in range(N):
    if temp is null:
        break
    temp = temp.next

💡 Deletion continues until N nodes are skipped or list ends.

delete

Delete node 9 by moving temp forward

Move 'temp' from node 9 to node 10, marking node 9 for deletion.

💡 Continue skipping nodes to delete them.

Line:

for _ in range(N):
    if temp is null:
        break
    temp = temp.next

💡 Deletion window expands as temp moves forward.

delete

Delete node 10 by moving temp forward

Move 'temp' from node 10 to null, marking node 10 for deletion and reaching list end.

💡 Deletion ends when temp reaches null or N nodes are skipped.

Line:

for _ in range(N):
    if temp is null:
        break
    temp = temp.next

💡 Deletion window ends at list end, no more nodes to process.

connect

Link current node to node after deleted nodes (null)

Set 'current.next' to 'temp' (null), removing nodes 8,9,10 from the list and ending it at node 7.

💡 Linking to null terminates the list properly after deletions.

Line:

current.next = temp

💡 Final link update completes the deletion process.

advance

Move current pointer to null to end loop

Set 'current' to 'temp' (null), indicating the end of the list and stopping the loop.

💡 When current is null, the algorithm finishes processing all nodes.

Line:

current = temp

💡 The algorithm terminates after processing the entire list.

reconstruct

Traversal complete, return modified list head

The algorithm returns the head of the modified list, which now excludes deleted nodes.

💡 Returning head allows reading the final list after all deletions.

Line:

return head

💡 The final list contains only nodes kept after skipping and deleting.

class ListNode:
    def __init__(self, val=0, next=null):
        self.val = val
        self.next = next

def delete_n_after_m_optimized(head, M, N):
    current = head  # STEP 1
    while current:
        for _ in range(1, M):  # STEP 2, 9
            if current is null:
                return head
            current = current.next
        if current is null:  # STEP 3
            break
        temp = current.next  # STEP 3, 10
        for _ in range(N):  # STEP 4-6, 11-13
            if temp is null:
                break
            temp = temp.next
        current.next = temp  # STEP 7, 14
        current = temp  # STEP 8, 15
    return head  # STEP 16

if __name__ == '__main__':
    nodes = [ListNode(i) for i in range(1, 11)]
    for i in range(9):
        nodes[i].next = nodes[i+1]
    head = nodes[0]
    M, N = 2, 3
    new_head = delete_n_after_m_optimized(head, M, N)
    curr = new_head
    res = []
    while curr:
        res.append(curr.val)
        curr = curr.next
    print(res)  # Expected: [1, 2, 6, 7]

📊

Delete N Nodes After M Nodes - Watch the Algorithm Execute, Step by Step

Watching each pointer movement and link change helps you understand how the algorithm efficiently deletes nodes in groups without extra space.

advance

1

→

2

→

3

→

4

→

5

→

6

→

7

→

8

→

9

→

10

advance

1

→

2

→

3

→

4

→

5

→

6

→

7

→

8

→

9

→

10

advance

1

→

2

→

3

→

4

→

5

→

6

→

7

→

8

→

9

→

10

advance

1

→

2

→

3

→

4

→

5

→

6

→

7

→

8

→

9

→

10

advance

1

→

2

→

3

→

4

→

5

→

6

→

7

→

8

→

9

→

10

advance

1

→

2

→

3

→

4

→

5

→

6

→

7

→

8

→

9

→

10

connect

1

→

2

→

3

→

4

→

5

→

6

→

7

→

8

→

9

→

10

advance

1

→

2

→

3

→

4

→

5

→

6

→

7

→

8

→

9

→

10

advance

1

→

2

→

3

→

4

→

5

→

6

→

7

→

8

→

9

→

10

advance

1

→

2

→

3

→

4

→

5

→

6

→

7

→

8

→

9

→

10

advance

1

→

2

→

3

→

4

→

5

→

6

→

7

→

8

→

9

→

10

advance

1

→

2

→

3

→

4

→

5

→

6

→

7

→

8

→

9

→

10

advance

1

→

2

→

3

→

4

→

5

→

6

→

7

→

8

→

9

→

10

connect

1

→

2

→

3

→

4

→

5

→

6

→

7

→

8

→

9

→

10

advance

1

→

2

→

3

→

4

→

5

→

6

→

7

→

8

→

9

→

10

reconstruct

1

→

2

→

3

→

4

→

5

→

6

→

7

→

8

→

9

→

10

Result: [1, 2, 6, 7]

Key Takeaways

✓ The algorithm efficiently skips M nodes and deletes N nodes repeatedly without extra space.

This insight is hard to see from code alone because the pointer movements and link updates are subtle and happen in a loop.

✓ Using two pointers 'current' and 'temp' clearly separates the nodes to keep from nodes to delete.

Visualizing these pointers helps understand how the algorithm isolates deletion segments.

✓ Link updates after deletion are the critical step that removes nodes from the list.

Seeing the link change visually clarifies how nodes are removed without traversing or copying the entire list.

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 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

3. What is the time complexity of the optimized fast and slow pointer approach for detecting a circular array loop in an array of length n?

medium

A. O(n^2) because each element may be visited multiple times

B. O(n log n) due to repeated modulo operations and pointer jumps

C. O(n) because each element is visited at most once due to marking visited elements

D. O(n) amortized but worst case can be O(n^2) if cycles overlap

Solution

1. Step 1: Identify outer loop and inner pointer movements

   The outer loop runs n times, but elements are marked zero once visited, preventing reprocessing.

2. Step 2: Analyze pointer visits

   Each element is visited at most once in the inner while loop due to zero marking, so total work is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Marking visited elements ensures linear time complexity [OK]

Hint: Marking visited elements prevents repeated work -> O(n) [OK]

Common Mistakes:

• Assuming repeated visits cause O(n^2)
• Confusing modulo cost as log factor
• Believing overlapping cycles increase complexity

4. Suppose the linked list can have multiple cycles due to node reuse (e.g., a node's next pointer can point to any previously visited node, creating multiple cycle entries). Which modification to Floyd's algorithm correctly detects the first cycle start node encountered from the head?

hard

A. Run Floyd's algorithm repeatedly after removing detected cycles until no cycle remains.

B. Use two pointers but move fast pointer three steps at a time to detect multiple cycles faster.

C. Modify Floyd's algorithm to reset the fast pointer to head after detection and continue until slow and fast meet again.

D. Use a hash set to track visited nodes and return the first repeated node encountered during traversal.

Solution

1. Step 1: Understand multiple cycles scenario

   Floyd's algorithm assumes a single cycle; multiple cycles break its assumptions and can cause incorrect detection.

2. Step 2: Use hash set to detect first repeated node

   Tracking visited nodes with a hash set detects the first node that appears twice, correctly identifying the earliest cycle entry.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Hash set approach works correctly with multiple cycles but uses extra space [OK]

Hint: Floyd's algorithm fails with multiple cycles; hash set detects first repeated node [OK]

Common Mistakes:

• Trying to adapt Floyd's algorithm without extra space
• Assuming multiple cycles can't exist
• Increasing fast pointer speed doesn't help

5. Suppose you want to find the middle node of a linked list, but the list is circular (the last node points back to the head). Which modification to the two-pointer approach correctly finds the middle node without infinite looping?

hard

A. Use the same two-pointer approach but add a visited set to detect cycles and stop when fast pointer revisits a node.

B. Use recursion to count nodes until the head is reached again, then find middle by index.

C. Convert the circular list to a linear list by breaking the cycle first, then apply the standard two-pointer approach.

D. Modify the loop to stop when fast or fast.next equals the head node, then return slow pointer.

Solution

1. Step 1: Understand circular list behavior

   In a circular list, fast pointer will loop infinitely unless we detect when it cycles back to head.

2. Step 2: Modify loop condition

   Stop when fast or fast.next equals head to avoid infinite loop; slow pointer will be at middle.

3. Step 3: Compare alternatives

   Visited set adds extra space; breaking cycle modifies input; recursion risks stack overflow.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Stopping at head detects cycle end without extra space [OK]

Hint: Detect cycle by checking if fast pointer returns to head [OK]

Common Mistakes:

• Using visited set wastes space
• Breaking cycle modifies input
• Recursion risks stack overflow