Delete N Nodes After M Nodes of a Linked List - Solution & Explanation

Problem Overview: Given a linked list, keep the first m nodes, delete the next n nodes, and repeat this pattern until the end of the list. The structure of the list must be modified in-place by updating node pointers.

Approach 1: Iterative Simulation (O(n) time, O(1) space)

The most direct strategy is to simulate the process exactly as described. Start from the head and iterate through the list using a pointer. First move forward m-1 steps to reach the last node that should be kept. From that node, skip the next n nodes by advancing another pointer and reconnect the kept node to the node that appears after the deleted segment. This works because a linked list allows efficient pointer rewiring without shifting elements. The entire list is traversed once, giving O(n) time complexity and O(1) extra space.

The key insight is that deletion in a singly linked list does not require removing nodes individually. Instead, you simply move a pointer n steps ahead and reconnect the previous node to the next valid node. This avoids repeated deletion operations and keeps the logic linear and efficient.

Approach 2: Simulation with Helper Pointer (O(n) time, O(1) space)

A small variation introduces a helper pointer to handle the skipping phase more cleanly. After traversing m nodes with the main pointer, use another pointer to advance through the next n nodes. Once the deletion block ends, update current.next to the node reached by the helper pointer. This separates the "keep" phase and "delete" phase, which can make the code easier to reason about during interviews.

This approach still performs a single pass over the list. Each node is visited at most once while either being counted among the kept nodes or skipped among the deleted nodes. The algorithm remains O(n) time and O(1) space since no additional data structures are required.

Both strategies rely purely on pointer traversal, a core skill when working with linked list problems. The pattern is similar to pointer-walking techniques used in two pointers problems, except both pointers move forward along the same list rather than from opposite ends.

Recommended for interviews: The iterative simulation approach is what interviewers typically expect. It directly mirrors the problem statement and demonstrates comfort with pointer manipulation in linked lists. Explaining how pointer rewiring skips entire blocks of nodes shows a clear understanding of list structure and leads to the optimal O(n) time, O(1) space solution.