Delete N Nodes After M Nodes of a Linked List

Easy · Linked List · Explanation and code example

Traverse Linked List and Delete In Place

How it works

The problem asks us to keep the first m nodes, then delete the next n nodes, and repeat this pattern throughout the linked list. Since we are modifying the list in place, we need to track two key positions: the last node we want to keep (the m-th node in each group) and the node that comes after the n deleted nodes. By linking these two positions, we effectively skip over the deleted nodes.

Steps

  1. Initialize two pointers: currentNode starting at the head, and lastMNode to track the last node we want to keep.
  2. While currentNode is not null:
    • Traverse m nodes while updating lastMNode to point to each node. After this loop, lastMNode points to the m-th node.
    • Traverse n more nodes. These are the nodes to be deleted.
    • Link lastMNode.next to currentNode, effectively removing the n nodes from the list.
  3. Return the head of the modified list.

Complexity

  • Time complexity: O(N)
  • Space complexity: O(1)

Where N is the length of the linked list pointed by head.

Things to watch for

Forgetting to Handle the End of the List

When traversing through m nodes to keep or n nodes to delete, you must check for null at each step. If the list ends before completing a full cycle, failing to check will cause a null pointer exception.

Not Updating the lastMNode Pointer Before Deletion

The lastMNode pointer must be updated during the "keep m nodes" phase, not after. If you forget to track the last kept node, you cannot properly link it to the node after the deleted segment.

Python code example

from typing import Optional

class Solution:
    def deleteNodes(self, head: Optional[ListNode], m: int, n: int) -> Optional[ListNode]:
        current_node = head
        last_m_node = head

        while current_node is not None:
            # initialize m_count to m and n_count to n
            m_count, n_count = m, n

            # traverse m nodes
            while current_node is not None and m_count != 0:
                last_m_node = current_node
                current_node = current_node.next
                m_count -= 1

            # traverse n nodes
            while current_node is not None and n_count != 0:
                current_node = current_node.next
                n_count -= 1

            # delete n nodes
            last_m_node.next = current_node

        return head

C++ code example

class Solution {
public:
    ListNode* deleteNodes(ListNode* head, int m, int n) {
        ListNode* currentNode = head;
        ListNode* lastMNode = head;

        while (currentNode != nullptr) {
            // initialize mCount to m and nCount to n
            int mCount = m, nCount = n;

            // traverse m nodes
            while (currentNode != nullptr && mCount != 0) {
                lastMNode = currentNode;
                currentNode = currentNode->next;
                mCount--;
            }

            // traverse n nodes
            while (currentNode != nullptr && nCount != 0) {
                currentNode = currentNode->next;
                nCount--;
            }

            // delete n nodes
            lastMNode->next = currentNode;
        }

        return head;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations