Delete N nodes after M nodes of a linked list

Summary

Given a singly linked list and two integers M and N, delete every Nth node starting from the (M+1)th node. This problem is about manipulating a linked list using a specific algorithm.

Detailed Explanation

To solve this problem, we'll iterate through the linked list until we reach the (M+1)th node. Then, we'll start deleting every Nth node after that point. Here's the step-by-step approach:

Initialize two pointers: current and prev. Set current to the head of the linked list.
Move current M nodes ahead by iterating M-1 times. Update prev accordingly.
Start a loop that continues until there are less than N nodes left in the list:
- Move current N nodes ahead by iterating N-1 times. Update prev.
- Delete the node pointed to by current. Move prev and current one step forward.
Return the modified linked list.

Here's an ASCII art diagram illustrating the process:

 1 -> 2 -> 3 -> 4 -> 5
    ^           ^
    | M nodes   | N nodes
    | ahead     |
    v           v
  x -> y -> z -> ...

Time complexity: O(L), where L is the length of the linked list. Space complexity: O(1) as we're only using a constant amount of space.

Optimized Solutions

Java

public class Solution { public ListNode deleteNodes(ListNode head, int M, int N) { if (head == null || M < 0 || N <= 0) return head; for (int i = 1; i < M; i++) { head = head.next; } ListNode prev = head; while (prev.next != null) { for (int i = 1; i < N; i++) { prev = prev.next; } prev.next = prev.next.next; } return head; } }