Delete N Nodes After M Nodes of a Linked List

Problem Statement

In this problem, you are provided with the head of a singly linked list and two integers, m and n. Your task is to modify the linked list in such a way that, starting from the head, you retain the first m nodes and then delete the next n nodes. This process of keeping m nodes followed by removing n nodes continues repeatedly through the list until no more nodes can be processed. The output should be the head of the linked list after all modifications are performed according to the specified pattern of retention and deletion.

Examples

Example 1

Input:

head = [1,2,3,4,5,6,7,8,9,10,11,12,13], m = 2, n = 3

Output:

[1,2,6,7,11,12]

Explanation:

Keep the first (m = 2) nodes starting from the head of the linked List (1 ->2) show in black nodes.
Delete the next (n = 3) nodes (3 -> 4 -> 5) show in read nodes.
Continue with the same procedure until reaching the tail of the Linked List.
Head of the linked list after removing nodes is returned.

Example 2

Input:

head = [1,2,3,4,5,6,7,8,9,10,11], m = 1, n = 3

Output:

[1,5,9]

Explanation:

Head of linked list after removing nodes is returned.

Constraints

• The number of nodes in the list is in the range [1, 104].
• 1 <= Node.val <= 106
• 1 <= m, n <= 1000

Approach and Intuition

When approaching this problem, the key is to handle the linked list traversal and modification efficiently while keeping track of the nodes. Here’s the step-by-step approach:

1. Initialize a pointer, say current, to point to the head of the linked list.
2. Traverse the m nodes starting from the current node. This is to ensure these m nodes are retained.
   • For each of the m nodes, check if the current pointer is null which indicates the end of the list. If not, simply move the current pointer to the next node.
3. Once m nodes are retained, move to deleting the next n nodes. This necessitates careful manipulation of the list pointers.
   • Keep another pointer, let’s call it prev, which should always point to the last node that is not deleted (last of m retained nodes).
   • Now increment the current pointer through the next n nodes. For each node, ensure you adjust the link from prev to skip the node currently pointed to by current.
4. Continue the above two steps until you have traversed the entire list or until the current pointer is null.
5. Return the modified linked list starting from the head.

The intuition here is to effectively manage the pointers as you traverse the list so that you can skip over the n nodes without losing the reference to the part of the list you need to retain. Also, it’s crucial to maintain an efficient approach to not revisit nodes unnecessarily which would otherwise increase the time complexity.

Solutions

class Solution {
public:
    ListNode* removeNodes(ListNode* head, int m, int n) {
        ListNode* current = head;
        ListNode* previousMNode = head;
        while (current != nullptr) {
            int keepCount = m, deleteCount = n;
            while (current != nullptr && keepCount != 0) {
                previousMNode = current;
                current = current->next;
                keepCount--;
            }
            while (current != nullptr && deleteCount != 0) {
                current = current->next;
                deleteCount--;
            }
            previousMNode->next = current;
        }
        return head;    
    }
};