Delete N Nodes After M Nodes in a Linked List (Leetcode Premium Problem)

 

Delete N Nodes After M Nodes in a Linked List

Difficulty Level: Rookie

In this problem, you are given a linked list and two integers, M and N. You need to traverse the linked list such that you:

1. Retain M nodes, then

2. Delete the next N nodes, and

3. Repeat this process until the end of the linked list.

---

Problem Statement

• Input: A linked list and two integers M and N

• Output: The modified linked list after deleting N nodes after every M nodes

Sample Inputs and Outputs

Sample Input 1:

M = 2, N = 2
Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

Sample Output 1:

1 -> 2 -> 5 -> 6

Explanation:

• Keep first 2 nodes: 1, 2

• Delete next 2 nodes: 3, 4

• Keep next 2 nodes: 5, 6

• Delete next 2 nodes: 7, 8

---

Sample Input 2:

M = 3, N = 2
Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

Sample Output 2:

1 -> 2 -> 3 -> 6 -> 7 -> 8

Explanation:

• Keep first 3 nodes: 1, 2, 3

• Delete next 2 nodes: 4, 5

• Keep next 3 nodes: 6, 7, 8

• Delete next 2 nodes: 9, 10

---

Algorithm

1. Traverse the linked list.

2. Skip M nodes.

3. Delete N nodes by skipping them and connecting the M-th node to the node after N deletions.

4. Repeat until the end of the linked list.
   
   

Java Code Implementation:

class ListNode {

    int val;

    ListNode next;

    ListNode(int val) { this.val = val; }

}

public class LinkedList {

    public static ListNode deleteNAfterM(ListNode head, int M, int N) {

        ListNode current = head;

        while (current != null) {

            // Step 1: Skip M nodes

            for (int i = 1; i < M && current != null; i++) {

                current = current.next;

            }

            if (current == null) break;

            // Step 2: Delete next N nodes

            ListNode temp = current.next;

            for (int i = 0; i < N && temp != null; i++) {

                temp = temp.next;

            }

            // Connect current node to the node after deleted nodes

            current.next = temp;

            // Step 3: Move current to next segment

            current = temp;

        }

        return head;

    }

    // Utility function to print linked list

    public static void printList(ListNode head) {

        ListNode temp = head;

        while (temp != null) {

            System.out.print(temp.val);

            if (temp.next != null) System.out.print(" -> ");

            temp = temp.next;

        }

        System.out.println();

    }

    public static void main(String[] args) {

        // Example: M=2, N=2, LL: 1->2->3->4->5->6->7->8

        ListNode head = new ListNode(1);

        head.next = new ListNode(2);

        head.next.next = new ListNode(3);

        head.next.next.next = new ListNode(4);

        head.next.next.next.next = new ListNode(5);

        head.next.next.next.next.next = new ListNode(6);

        head.next.next.next.next.next.next = new ListNode(7);

        head.next.next.next.next.next.next.next = new ListNode(8);

        int M = 2, N = 2;

        head = deleteNAfterM(head, M, N);

        printList(head); // Output: 1 -> 2 -> 5 -> 6

    }

}

✅ Key Points

• Always check for null to avoid runtime errors.

• Works for any values of M and N, including 0.

• Simple and intuitive using two loops: one to skip M nodes, one to delete N nodes.