Delete N Nodes After M Nodes of a Linked List

Problem Description

Ah, the classic “Delete N Nodes After M Nodes of a Linked List” problem! It’s like trying to manage a party guest list where you invite M friends, but after that, you decide to kick out N of them. Why? Because they brought kale chips instead of nachos, obviously!

In this problem, you are given a linked list and two integers, M and N. Your task is to keep M nodes and then delete the next N nodes. Repeat this process until you reach the end of the list. It’s like a game of musical chairs, but instead of chairs, you have nodes, and instead of music, you have your questionable decision-making skills.

Code Solution


class Solution:
    def deleteNodes(
        self,
        head: ListNode | None,
        m: int,
        n: int,
    ) -> ListNode | None:
        curr = head
        prev = None  # prev.next == curr

        while curr:
            # Set the m-th node as `prev`.
            for _ in range(m):
                if not curr:
                    break
                prev = curr
                curr = curr.next
            # Set the (m + n + 1)-th node as `curr`.
            for _ in range(n):
                if not curr:
                    break
                curr = curr.next
            # Delete the nodes [m + 1..n - 1].
            prev.next = curr

        return head

Approach

The approach is straightforward: traverse the linked list while keeping track of the current node and the previous node. For every M nodes, we keep them, and for the next N nodes, we simply skip them. This is done using two nested loops: one for keeping nodes and another for deleting nodes. It’s like a well-choreographed dance, but with less grace and more pointers.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(L), where L is the length of the linked list. We traverse the list once.
Space Complexity	O(1), as we are using a constant amount of space regardless of the input size.

Real-World Example

Imagine you’re at a buffet. You can take M servings of delicious food, but after that, you have to skip N servings of the not-so-delicious kale salad. You keep doing this until the buffet runs out of food. This is exactly what our code does with the linked list: it keeps M nodes (the good stuff) and skips N nodes (the kale salad).