Delete N Nodes After M Nodes of a Linked List

Easy
2000.

Delete N Nodes After M Nodes of a Linked List

Delete N Nodes After M Nodes of a Linked List is an easy coding problem on simulation, asked in Amazon and Microsoft interviews.

You are given the head of a singly linked list and two integers m and n. Walk the list from the head and repeat this pattern until the list runs out:

  • keep the next m nodes,
  • then delete the next n nodes.

If the list ends in the middle of either step, simply stop. Return the head of the list after the deletions.

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 1,2; delete 3,4,5; keep 6,7; delete 8,9,10; keep 11,12; delete 13.

Example 2

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

Example 3

Input
head = [7,3,5], m = 4, n = 2
Output
[7,3,5]
Explanation
The list ends while still keeping, so nothing is deleted.

Constraints

  • 1 <= number of nodes <= 10^4
  • 1 <= Node.val <= 10^6
  • 1 <= m, n <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for singly-linked list (provided by the judge — do not redefine it):
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} m
 * @param {number} n
 * @return {ListNode}
 */
var deleteNodes = function(head, m, n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Delete N Nodes After M Nodes of a Linked List — Solution

Delete N Nodes After M Nodes of a Linked List solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Delete N Nodes After M Nodes of a Linked List is an easy coding problem on simulation, asked in Amazon and Microsoft interviews.

  • Difficulty: Easy
  • Topics: Simulation
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given the head of a singly linked list and two integers m and n. Walk the list from the head and repeat this pattern until the list runs out:

  • keep the next m nodes,
  • then delete the next n nodes.

If the list ends in the middle of either step, simply stop. Return the head of the list after the deletions.

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 1,2; delete 3,4,5; keep 6,7; delete 8,9,10; keep 11,12; delete 13.

Example 2

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

Example 3

Input: head = [7,3,5], m = 4, n = 2
Output: [7,3,5]
Explanation: The list ends while still keeping, so nothing is deleted.

Constraints

  • 1 <= number of nodes <= 10^4
  • 1 <= Node.val <= 10^6
  • 1 <= m, n <= 1000

Hints for Delete N Nodes After M Nodes of a Linked List

  1. Hint 1

    The pattern repeats every m + n nodes.

  2. Hint 2

    Walk m - 1 steps to the last node you keep, then walk past the next n nodes.

  3. Hint 3

    Link the last kept node directly to the node after the deleted block, and start the next round from there. Stop as soon as a pointer becomes null.

How to solve Delete N Nodes After M Nodes of a Linked List

Each round keeps a block of m nodes and cuts out the following block of n. Cutting a block out of a singly linked list is one pointer change: link the block's predecessor to its successor.

Approach

  1. Set cur = head.
  2. While cur is not null: advance cur m - 1 times (stopping if it becomes null) — cur is now the last kept node of this round.
  3. From cur.next, skip n nodes (stopping at null) to reach after.
  4. Set cur.next = after and cur = after; repeat.
  5. Return head — the first node is always kept because m >= 1.

Why it works

Every round starts at the first node of a fresh keep-block, keeps exactly m nodes (or fewer if the list ends) and removes exactly the next n, which is precisely the pattern. Each node is visited once.

Complexity

  • Time — O(L) for a list of L nodes
  • Space — O(1)

Pitfalls

  • The list may end inside the keep block; check for null while advancing m - 1 steps.
  • The list may end inside the delete block; after is then null and the list simply ends at cur.
  • Off by one: reaching the last kept node takes m - 1 steps, not m.

Reference solution

Python

from typing import Optional

def deleteNodes(head: Optional[ListNode], m: int, n: int) -> Optional[ListNode]:
    cur = head
    while cur:
        for _ in range(m - 1):
            if cur is None:
                break
            cur = cur.next
        if cur is None:
            break
        after = cur.next
        for _ in range(n):
            if after is None:
                break
            after = after.next
        cur.next = after
        cur = after
    return head

Java

public static ListNode deleteNodes(ListNode head, int m, int n) {
    ListNode cur = head;
    while (cur != null) {
        for (int i = 1; i < m && cur != null; i++) cur = cur.next;
        if (cur == null) break;
        ListNode after = cur.next;
        for (int j = 0; j < n && after != null; j++) after = after.next;
        cur.next = after;
        cur = after;
    }
    return head;
}

C++

ListNode* deleteNodes(ListNode* head, int m, int n) {
    ListNode* cur = head;
    while (cur) {
        for (int i = 1; i < m && cur; i++) cur = cur->next;
        if (!cur) break;
        ListNode* after = cur->next;
        for (int j = 0; j < n && after; j++) after = after->next;
        cur->next = after;
        cur = after;
    }
    return head;
}

JavaScript

var deleteNodes = function(head, m, n) {
    var cur = head;
    while (cur !== null) {
        for (var i = 1; i < m && cur !== null; i++) cur = cur.next;
        if (cur === null) break;
        var after = cur.next;
        for (var j = 0; j < n && after !== null; j++) after = after.next;
        cur.next = after;
        cur = after;
    }
    return head;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 137 simulation problems · the whole catalogue