💬 Discord
Sign In
NeetCode #311LC-1474EasyLinked ListNC Algo100
← Back to All Problems

#311 · #1474 · Delete N Nodes After M Nodes of a Linked List(删除链表 M 个节点之后的 N 个节点)

📌 Problem Statement & Constraints

Given the head of a linked list and two integers m and n, traverse the list and delete n nodes after keeping m nodes, repeating until the end. Return the head. Constraints: 1 <= m, n <= 1000, the number of nodes is at most 10^4.

💡 Core Algorithmic Approaches

  1. Keep a pointer cur at the last node of a kept block.
  2. Advance m - 1 steps to reach the end of the kept block, then skip n nodes to find the next kept node.
  3. Link cur.next to that node and continue.
  4. The loop terminates when there are no more nodes to process.

💻 Benchmark Python3 Implementation

class Solution:
    def deleteNodes(self, head: Optional[ListNode], m: int, n: int) -> Optional[ListNode]:
        cur = head
        while cur:
            # keep m nodes: advance m-1 from cur
            for _ in range(m - 1):
                if cur is None:
                    break
                cur = cur.next
            if cur is None:
                break
            # delete the next n nodes
            nxt = cur.next
            for _ in range(n):
                if nxt is None:
                    break
                nxt = nxt.next
            cur.next = nxt                 # relink past the deleted block
            cur = nxt
        return head

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(L): each node is visited once.
💾 Space Complexity
O(1): pointer manipulation only.

⚠️ Interview Pitfalls & Follow-ups

  • Advancing m steps instead of m - 1: cur starts at the first kept node, so only m - 1 further steps are needed.
  • Deleting n + 1 nodes: the block to delete is exactly n nodes after the kept block.
  • Forgetting the None guards: the list may end in the middle of a kept or deleted block.
  • Building a new list: the nodes should be relinked in place.