Delete N Nodes After M Nodes of a Linked List

curriculum-variant — keep m, delete n, repeat throughout the list.

Easy
Time O(L) Space O(1)
4 min read
linked-list

Problem#

(no canonical LeetCode entry.) Given a list, repeatedly keep m nodes and delete the next n until the list ends.

Examples#

  • head = [1,2,3,4,5,6,7,8,9,10,11,12,13], m = 2, n = 3[1,2,6,7,11,12]
  • head = [1,2,3,4,5,6,7,8,9,10,11], m = 1, n = 3[1,5,9]

Constraints#

  • 1 <= m, n <= 1000.

Approach#

Walk in alternating phases: keep m, then unlink n, then repeat until null.

Solution#

Delete N After M
ListNode* deleteNAfterM(ListNode* head, int m, int n) {
ListNode* curr = head;
while (curr) {
// Skip m - 1 nodes (curr counts as 1).
for (int i = 1; i < m && curr; ++i) curr = curr->next;
if (!curr) break;
// Delete next n nodes.
ListNode* del = curr->next;
for (int i = 0; i < n && del; ++i) {
ListNode* nxt = del->next;
delete del;
del = nxt;
}
curr->next = del;
curr = del;
}
return head;
}

Editorial#

The asymmetric counters are the gotcha: curr already counts as the first of m kept nodes, so we skip m - 1 more. Then we splice past n nodes by chaining their deallocations. The del walk handles “list shorter than n” via the loop guard.

Complexity#

  • Time: O(L).
  • Space: O(1).

Concept revision#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.