Delete N Nodes After M Nodes of a Linked List

Problem

You are given the head of a linked list and two integers m and n.

Traverse the linked list and remove some nodes in the following way:

• Start with the head as the current node.
• Keep the first m nodes starting with the current node.
• Remove the next n nodes
• Keep repeating steps 2 and 3 until you reach the end of the list.

Return the head of the modified list after removing the mentioned nodes.

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, 10^4].
• 1 <= Node.val <= 10^6
• 1 <= m, n <= 1000

Follow up: Could you solve this problem by modifying the list in-place?

Solution

Method 1 – Iterative Linked List Traversal

Intuition

We can solve this problem by traversing the linked list and, for each segment, keeping the first m nodes and then deleting the next n nodes. We repeat this process until the end of the list. This approach modifies the list in-place and is efficient for large lists.

Approach

1. Initialize a pointer cur to the head of the list.
2. While cur is not null:
   • Move cur forward m-1 times to keep the first m nodes (if possible).
   • If cur is null after this, break.
   • Initialize a pointer tmp to cur.next and move it forward n times to skip the next n nodes.
   • Set cur.next = tmp to delete the skipped nodes.
   • Move cur to tmp and repeat.
3. Return the head of the modified list.

Code

C++

class Solution {
public:
    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* tmp = cur->next;
            for (int i = 0; i < n && tmp; ++i) tmp = tmp->next;
            cur->next = tmp;
            cur = tmp;
        }
        return head;
    }
};

Go

func deleteNodes(head *ListNode, m int, n int) *ListNode {
    cur := head
    for cur != nil {
        for i := 1; i < m && cur != nil; i++ {
            cur = cur.Next
        }
        if cur == nil {
            break
        }
        tmp := cur.Next
        for i := 0; i < n && tmp != nil; i++ {
            tmp = tmp.Next
        }
        cur.Next = tmp
        cur = tmp
    }
    return head
}

Java

class Solution {
    public 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 tmp = cur.next;
            for (int i = 0; i < n && tmp != null; i++) tmp = tmp.next;
            cur.next = tmp;
            cur = tmp;
        }
        return head;
    }
}

Kotlin

class Solution {
    fun deleteNodes(head: ListNode?, m: Int, n: Int): ListNode? {
        var cur = head
        while (cur != null) {
            for (i in 1 until m) {
                if (cur?.next == null) return head
                cur = cur.next
            }
            var tmp = cur?.next
            for (i in 0 until n) {
                if (tmp == null) break
                tmp = tmp.next
            }
            cur?.next = tmp
            cur = tmp
        }
        return head
    }
}

Python

class Solution:
    def deleteNodes(self, head: 'ListNode', m: int, n: int) -> 'ListNode':
        cur = head
        while cur:
            for _ in range(m - 1):
                if not cur:
                    return head
                cur = cur.next
            if not cur:
                break
            tmp = cur.next
            for _ in range(n):
                if not tmp:
                    break
                tmp = tmp.next
            cur.next = tmp
            cur = tmp
        return head

Rust

impl Solution {
    pub fn delete_nodes(mut head: Option<Box<ListNode>>, m: i32, n: i32) -> Option<Box<ListNode>> {
        let mut cur = head.as_mut();
        while let Some(node) = cur {
            for _ in 1..m {
                if node.next.is_none() { return head; }
                cur = node.next.as_mut();
                if let Some(nxt) = cur { cur = Some(nxt); } else { break; }
            }
            let mut tmp = cur.and_then(|node| node.next.as_mut());
            for _ in 0..n {
                if tmp.is_none() { break; }
                tmp = tmp.and_then(|node| node.next.as_mut());
            }
            if let Some(node) = cur {
                node.next = tmp.map(|n| Box::new((**n).clone()));
                cur = node.next.as_mut();
            }
        }
        head
    }
}

TypeScript

class Solution {
    deleteNodes(head: ListNode | null, m: number, n: number): ListNode | null {
        let cur = head;
        while (cur) {
            for (let i = 1; i < m && cur; i++) cur = cur.next;
            if (!cur) break;
            let tmp = cur.next;
            for (let i = 0; i < n && tmp; i++) tmp = tmp.next;
            cur.next = tmp;
            cur = tmp;
        }
        return head;
    }
}

Complexity

• ⏰ Time complexity: O(n), where n is the number of nodes in the list, since each node is visited at most once.
• 🧺 Space complexity: O(1), as we only use a constant amount of extra space.