Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def deleteNodes(head: ListNode, m: int, n: int) -> ListNode:
    curr = head
    while curr:
        # Skip m nodes
        for i in range(1, m):
            if curr is None:
                return head
            curr = curr.next
        if curr is None:
            break
        # Delete next n nodes
        temp = curr.next
        for j in range(n):
            if temp is None:
                break
            temp = temp.next
        curr.next = temp
        curr = temp
    return head
      

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
ListNode* deleteNodes(ListNode* head, int m, int n) {
    ListNode* curr = head;
    while (curr) {
        // Skip m-1 nodes
        for (int i = 1; i < m && curr; ++i)
            curr = curr->next;
        if (!curr)
            break;
        // Delete next n nodes
        ListNode* temp = curr->next;
        for (int j = 0; j < n && temp; ++j)
            temp = temp->next;
        curr->next = temp;
        curr = temp;
    }
    return head;
}
      

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public ListNode deleteNodes(ListNode head, int m, int n) {
    ListNode curr = head;
    while (curr != null) {
        // Skip m-1 nodes
        for (int i = 1; i < m && curr != null; i++) {
            curr = curr.next;
        }
        if (curr == null) break;
        // Delete next n nodes
        ListNode temp = curr.next;
        for (int j = 0; j < n && temp != null; j++) {
            temp = temp.next;
        }
        curr.next = temp;
        curr = temp;
    }
    return head;
}
      

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
var deleteNodes = function(head, m, n) {
    let curr = head;
    while (curr) {
        // Skip m-1 nodes
        for (let i = 1; i < m && curr; i++) {
            curr = curr.next;
        }
        if (!curr) break;
        // Delete next n nodes
        let temp = curr.next;
        for (let j = 0; j < n && temp; j++) {
            temp = temp.next;
        }
        curr.next = temp;
        curr = temp;
    }
    return head;
};
      

Problem Description

Given the head of a singly linked list, and two integers m and n, the task is to modify the list such that after keeping the first m nodes, you delete the next n nodes. You repeat this process until you reach the end of the list.

The function should return the head of the modified linked list. You must not create new nodes or reuse deleted nodes; you should only change the next pointers to achieve the result.

• There is only one valid way to perform the deletion as described.
• All node values are unique and should not be reused.

Thought Process

To solve this problem, we need to traverse the linked list and alternate between keeping and deleting nodes. At first glance, one might consider copying the values into a new list, but this would violate the constraint of not creating or reusing nodes. Instead, we must manipulate the existing next pointers.

The brute-force approach would be to traverse the list, count nodes, and delete as needed, but this can be error-prone if not carefully managed. To optimize, we can use two pointers: one to skip the nodes to keep, and another to skip and remove the nodes to delete. This way, we ensure we only traverse each part of the list once.

The key insight is to carefully manage the pointers so that after skipping m nodes, we can link the last kept node directly to the node after the n nodes to be deleted.

Solution Approach

• Step 1: Start with a pointer at the head of the linked list.
• Step 2: For each cycle:
  • Move forward m-1 times (to keep m nodes). If you reach the end, stop.
  • Now, from this position, move forward n times to skip the nodes to be deleted. Again, if you reach the end, stop.
  • Link the last kept node's next pointer to the node after the last deleted node (or null if at the end).
• Step 3: Repeat until the end of the list is reached.

We use a single traversal, only updating pointers as needed, which is efficient and adheres to the problem's constraints.

Example Walkthrough

Suppose the input linked list is 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10, and m = 2, n = 3.

1. Start at node 1. Keep nodes 1 and 2.
2. Delete the next 3 nodes: 3, 4, 5. The list now looks like 1 -> 2 -> 6 -> 7 -> 8 -> 9 -> 10.
3. From node 2, move to node 6 and keep nodes 6 and 7.
4. Delete the next 3 nodes: 8, 9, 10. Since only 8, 9, 10 are left, all are deleted. The list now looks like 1 -> 2 -> 6 -> 7.
5. No more nodes to process, so we are done.

The final linked list is 1 -> 2 -> 6 -> 7.

Time and Space Complexity

• Brute-force Approach: If you tried to rebuild the list or use extra data structures, you would need O(N) extra space and O(N) time, where N is the number of nodes.
• Optimized Approach (pointer manipulation): We only traverse the list once, so the time complexity is O(N). No extra space is used (apart from a few pointers), so the space complexity is O(1).

The optimized approach is both time and space efficient because it works in-place and only requires a single pass through the list.

Summary

By carefully managing the traversal and pointer updates, we can efficiently delete every group of n nodes after every group of m nodes in a singly linked list. The key insight is to avoid unnecessary data structures and simply manipulate the next pointers as we traverse. This leads to an elegant, in-place, and optimal solution.