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
mnodes, - then delete the next
nnodes.
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^41 <= Node.val <= 10^61 <= m, n <= 1000
Hints for Delete N Nodes After M Nodes of a Linked List
Hint 1
The pattern repeats every
m + nnodes.Hint 2
Walk
m - 1steps to the last node you keep, then walk past the nextnnodes.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
- Set
cur = head. - While
curis not null: advancecurm - 1times (stopping if it becomes null) —curis now the last kept node of this round. - From
cur.next, skipnnodes (stopping at null) to reachafter. - Set
cur.next = afterandcur = after; repeat. - Return
head— the first node is always kept becausem >= 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 - 1steps. - The list may end inside the delete block;
afteris then null and the list simply ends atcur. - Off by one: reaching the last kept node takes
m - 1steps, notm.
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 headJava
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.