Delete N Nodes After M Nodes of a Linked List

Problem Description

Ah, the classic dilemma of managing a linked list! Imagine you’re at a party, and you’re trying to keep track of your friends. You decide to invite a few, but then you realize that some of them are just too much to handle. So, you invite M friends, and after that, you decide to kick out N of them. Rinse and repeat until you’re left with a manageable group.

In the world of linked lists, this translates to deleting N nodes after every M nodes. The task is to traverse the linked list, keep the first M nodes, and then delete the next N nodes. Sounds simple, right? Well, it’s like trying to keep your fridge organized after a grocery run—easier said than done!

Code Solution


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

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

    return head;
  }
};

Approach

The approach is straightforward: we traverse the linked list while maintaining two pointers. The first pointer (curr) helps us navigate through the list, while the second pointer (prev) keeps track of the last node we want to keep. After skipping M nodes, we then skip the next N nodes and link the last kept node to the next valid node. This process continues until we reach the end of the list.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(L), where L is the length of the linked list.
Space Complexity	O(1), as we are using a constant amount of space for pointers.

Real-World Example

Think of a group project where you have to present your work. You decide to let M people present their parts, but after that, you realize that N of them are just rambling on and on. So, you politely ask them to step aside. This is exactly what our code does with the linked list—keeping the good stuff and removing the noise!