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#
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;}func deleteNAfterM(head *ListNode, m, n int) *ListNode { curr := head for curr != nil { // Skip m - 1 nodes (curr counts as 1). for i := 1; i < m && curr != nil; i++ { curr = curr.Next } if curr == nil { break } // Delete next n nodes. del := curr.Next for i := 0; i < n && del != nil; i++ { del = del.Next } curr.Next = del curr = del } return head}from typing import Optional
class Solution: def deleteNAfterM(self, head: Optional['ListNode'], m: int, n: int) -> Optional['ListNode']: curr = head while curr: # Skip m - 1 nodes (curr counts as 1). for _ in range(m - 1): if not curr: break curr = curr.next if not curr: break # Delete next n nodes. delete = curr.next for _ in range(n): if not delete: break delete = delete.next curr.next = delete curr = delete return headfunction deleteNAfterM(head, m, n) { let curr = head; while (curr) { // Skip m - 1 nodes (curr counts as 1). for (let i = 1; i < m && curr; i++) curr = curr.next; if (!curr) break; // Delete next n nodes. let del = curr.next; for (let i = 0; i < n && del; i++) del = del.next; curr.next = del; curr = del; } return head;}class Solution { public ListNode deleteNAfterM(ListNode head, int m, int n) { ListNode curr = head; while (curr != null) { // Skip m - 1 nodes (curr counts as 1). for (int i = 1; i < m && curr != null; i++) curr = curr.next; if (curr == null) break; // Delete next n nodes. ListNode del = curr.next; for (int i = 0; i < n && del != null; i++) del = del.next; curr.next = del; curr = del; } return head; }}function deleteNAfterM(head: ListNode | null, m: number, n: number): ListNode | null { let curr = head; while (curr) { // Skip m - 1 nodes (curr counts as 1). for (let i = 1; i < m && curr; i++) curr = curr.next; if (!curr) break; // Delete next n nodes. let del: ListNode | null = curr.next; for (let i = 0; i < n && del; i++) del = del.next; 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#
Related#