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 a circular array where each element represents the number of steps to move forward or backward. The goal is to determine if there exists a cycle where all moves are in the same direction and the cycle length is greater than 1. Which algorithmic approach guarantees an optimal O(n) time and O(1) space solution for this problem?

easy

A. Fast and slow pointer technique (Floyd's cycle detection) adapted for circular arrays with direction checks

B. Greedy approach that tries to jump as far as possible each time without revisiting indices

C. Dynamic programming to store reachable indices and cycle lengths

D. Brute force simulation with a visited set for each start index

Solution

1. Step 1: Understand problem constraints

   The problem requires detecting cycles in a circular array with direction consistency and cycle length > 1.

2. Step 2: Identify algorithm that efficiently detects cycles

   Fast and slow pointer (Floyd's cycle detection) can detect cycles in O(n) time and O(1) space, with added direction checks to ensure cycle validity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Fast-slow pointer is classic for cycle detection in sequences [OK]

Hint: Cycle detection in sequences -> fast-slow pointer [OK]

Common Mistakes:

• Thinking greedy jumps detect cycles correctly
• Assuming DP applies here
• Using brute force is optimal

2. You are given a singly linked list that may contain a cycle. The task is to find the node where the cycle begins, if any. Which of the following approaches guarantees finding the cycle's start node in O(n) time and O(1) space?

easy

A. Use two pointers moving at different speeds to detect the cycle and then find the cycle start by resetting one pointer to head.

B. Use a depth-first search to detect back edges and identify the cycle start.

C. Use a hash set to store visited nodes and return the first repeated node.

D. Use a greedy approach to jump nodes and check for cycles by comparing node values.

Solution

1. Step 1: Understand cycle detection with two pointers

   The fast and slow pointer technique detects a cycle by moving fast pointer twice as fast as slow pointer. If they meet, a cycle exists.

2. Step 2: Find cycle start by resetting one pointer

   After detection, reset one pointer to head and move both one step at a time until they meet again; this meeting point is the cycle start node.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer approach finds cycle start in O(n) time and O(1) space [OK]

Hint: Two pointers detect and locate cycle start efficiently [OK]

Common Mistakes:

• Believing hash set is O(1) space
• Using DFS which is not suitable for linked lists
• Greedy jumps fail to detect cycles

3. What is the time complexity of the optimal Happy Number detection algorithm that uses a known cycle set and repeatedly computes the sum of squares of digits until it reaches 1 or a cycle number? Assume n is the input number and k is the number of iterations until termination.

medium

A. O(n) because each digit is processed once per iteration

B. O(k * log n) because each iteration processes digits proportional to log n and there are k iterations

C. O(k * n) because sum of squares depends on n itself

D. O(k) because the cycle detection set lookup is constant time and digits are fixed length

Solution

1. Step 1: Identify cost per iteration

   Each iteration computes sum of squares of digits. Number of digits in n is proportional to log n, so each iteration is O(log n).

2. Step 2: Multiply by number of iterations k

   The process repeats k times until reaching 1 or cycle. Total time is O(k * log n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum of digits per iteration is log n, repeated k times -> O(k * log n) [OK]

Hint: Sum of digits cost is O(log n), not O(n) [OK]

Common Mistakes:

• Confusing n with number of digits, assuming O(n) per iteration

4. Examine the following code snippet intended to detect the start of a cycle in a linked list. Identify the line containing the subtle bug that can cause a runtime error or infinite loop.

medium

A. Line 5: fast = fast.next.next

B. Line 3: while fast:

C. Line 7: if slow == fast:

D. Line 11: while ptr1 != ptr2:

Solution

1. Step 1: Check loop condition safety

   The loop condition only checks if fast is not None, but fast.next may be None, so fast.next.next can cause an exception.

2. Step 2: Identify fix

   The loop condition should check both fast and fast.next to avoid null pointer exceptions.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Accessing fast.next.next without checking fast.next causes runtime error [OK]

Hint: Always check fast and fast.next before accessing fast.next.next [OK]

Common Mistakes:

• Missing fast.next check
• Returning meeting point as cycle start
• Infinite loop due to wrong loop condition

5. What is the space complexity of the stack-based approach to find the nth node from the end in a singly linked list of length n?

medium

A. O(n) because all nodes are stored in the stack

B. O(1) because only a few pointers are used

C. O(n) because recursion stack is used

D. O(log n) due to divide and conquer traversal

Solution

1. Step 1: Identify data structures used

   The stack stores every node in the list, so it holds n nodes.

2. Step 2: Determine space complexity

   Storing all n nodes means O(n) auxiliary space is required.

3. Step 3: Re-examine options

   O(n) because all nodes are stored in the stack states O(n) space which is correct for stack-based approach. O(1) because only a few pointers are used states O(1) which is incorrect for stack-based approach.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Stack size grows linearly with list length [OK]

Hint: Stack stores all nodes, so space is O(n) [OK]

Common Mistakes:

• Assuming constant space due to pointers
• Confusing recursion stack with iterative stack
• Thinking divide and conquer applies here