Delete N Nodes After M Nodes of a Linked List

This problem can be solved by simulating the process described in the problem statement. We’ll traverse the linked list, keeping m nodes and then deleting n nodes.

Approach

1. Initialize two pointers, current and prev.
2. Traverse the list using a loop.
3. For each step, keep m nodes by simply moving the current pointer.
4. Delete n nodes by adjusting the next pointer of the prev node.
5. Repeat steps 3-4 until the end of the list.

Here’s the code implementing this approach:

 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

class Solution:
    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:
        current = head
        prev = None

        while current:
            # Keep m nodes
            for _ in range(m):
                prev = current
                current = current.next
                if not current:
                    break

            # Delete n nodes
            for _ in range(n):
                if current:
                    current = current.next
                else:
                    break

            # Update the next pointer of the previous node to skip n nodes
            if prev:
                prev.next = current

        return head

Example

Let’s take head = [1,2,3,4,5,6,7,8,9,10,11,12,13], m = 2, n = 3 as an example:

• Keep 2 nodes: 1,2.
• Delete 3 nodes: 3,4,5.
• Keep 2 nodes: 6,7.
• Delete 3 nodes: 8,9,10.
• Keep 2 nodes: 11,12.
• Result: [1,2,6,7,11,12].

Complexity

This solution has a time complexity of O(N) and a space complexity of O(1), where N is the number of nodes in the linked list.