Delete N Nodes After M Nodes of a Linked List

Problem Description

So, you’ve got a linked list, and it’s looking a bit too crowded. The task here is to delete N nodes after you’ve kept M nodes. Think of it as a party where you let M friends in, but after that, you’re like, “Sorry, no more room!” and you kick out N of them.

In more technical terms, given a linked list, you need to traverse it and keep M nodes, then delete the next N nodes, and repeat this process until you reach the end of the list.

Code Solution


class Solution {
  public ListNode deleteNodes(ListNode head, int m, int n) {
    ListNode curr = head;
    ListNode prev = null; // prev.next == curr

    while (curr != null) {
      // Set the m-th node as `prev`.
      for (int i = 0; i < m && curr != null; ++i) {
        prev = curr;
        curr = curr.next;
      }
      // Set the (m + n + 1)-th node as `curr`.
      for (int i = 0; i < n && curr != null; ++i)
        curr = curr.next;
      // Delete the nodes [m + 1..n - 1].
      prev.next = curr;
    }

    return head;
  }
}

Approach

The approach is straightforward: you traverse the linked list while keeping track of the current node and the previous node. For every M nodes you keep, you skip the next N nodes by adjusting the pointers. It’s like playing a game of musical chairs, but instead of chairs, you have nodes, and instead of music, you have a strict policy of “no more than M friends at a time!”

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(L), where L is the length of the linked list.
Space Complexity	O(1), since you’re only using a few pointers.

Real-World Example

Imagine you’re at a buffet. You can take M plates of food, but after that, you have to put down N plates before you can grab more. If you keep doing this, you’ll end up with a perfectly curated selection of dishes without overwhelming your table. This is exactly what the algorithm does with the linked list!