LeetCode Problem 1474

Difficulty: 🟢 Easy
Topics: Linked List

Solution

LeetCode 1474, Delete N Nodes After M Nodes of a Linked List

Problem Understanding

This problem gives us the head of a singly linked list and two integers, m and n. We must traverse the linked list while repeatedly applying a fixed pattern:

1. Keep the next m nodes.
2. Delete the following n nodes.
3. Continue repeating this process until the list ends.

The important detail is that the deletions happen in-place by reconnecting pointers in the linked list. We are not asked to create a new list containing the remaining values. Instead, we modify the existing linked structure.

For example, if the list is:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

and m = 2, n = 2, we:

• Keep 1, 2
• Delete 3, 4
• Keep 5, 6
• Delete 7

The final list becomes:

1 -> 2 -> 5 -> 6

The input consists of:

• head, the first node of the singly linked list
• m, the number of nodes to preserve in each cycle
• n, the number of nodes to remove after the preserved section

The output is the head of the modified linked list.

The constraints tell us that the list size can be as large as 10^4 nodes. This is small enough for a linear traversal solution, but large enough that repeatedly rebuilding lists or performing expensive operations would be unnecessary. Since this is a linked list problem, the intended solution is pointer manipulation.

Several edge cases are important:

• The list may end while we are still in the "keep" phase.
• The list may end while we are deleting nodes.
• m may equal 1, meaning we only preserve one node each cycle.
• n may be larger than the remaining number of nodes.
• The list may contain only one node.
• The constraints guarantee m >= 1, so we never need to handle the case where every node is deleted immediately.

The follow-up asks whether the solution can be done in-place. Since linked lists naturally support pointer rewiring, the optimal solution modifies the list directly without extra storage.

Approaches

Brute Force Approach

A brute force approach would first copy all node values into an array. Then we could simulate the keep/delete process using indices and build a second array containing only the preserved values. Finally, we would construct a completely new linked list from the filtered values.

This works because arrays make indexed traversal simple. We can easily determine which elements belong to "keep" sections and which belong to "delete" sections.

However, this approach is inefficient because:

• It uses extra memory proportional to the size of the list.
• It rebuilds the entire linked list unnecessarily.
• The problem specifically hints that an in-place solution is preferred.

Although the time complexity is still linear, the extra memory usage is avoidable.

Optimal In-Place Linked List Traversal

The key observation is that we never actually need to remove nodes one by one. Instead, after keeping m nodes, we can simply reconnect the next pointer of the last kept node to the node after the deleted section.

This works perfectly with linked lists because deleting a sequence of nodes only requires changing a single pointer.

The algorithm repeatedly performs two phases:

1. Move forward m - 1 times to reach the last node we want to keep.
2. Skip the next n nodes by reconnecting pointers.

Since each node is visited at most once, the solution runs in linear time and constant extra space.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Copies values into arrays and rebuilds the list
Optimal	O(n)	O(1)	Modifies pointers directly in-place

Algorithm Walkthrough

1. Start with a pointer called current pointing to the head of the linked list.
2. Traverse the next m - 1 nodes because we want to preserve exactly m nodes in each cycle. After this traversal, current points to the last node that should remain in the list.
3. If current becomes None during the keep phase, we have reached the end of the list and can stop immediately.
4. Create another pointer called temp starting from current.next. This pointer will move across the nodes that must be deleted.
5. Move temp forward n times to skip the nodes that should be removed. If the list ends before finishing the deletion phase, that is acceptable.
6. Reconnect the list by setting:

current.next = temp

This effectively removes all skipped nodes from the linked list.

1. Move current to temp and repeat the process until the end of the list is reached.

Why it works

The algorithm maintains the invariant that every node before current has already been processed correctly according to the keep/delete pattern. During each cycle, we preserve exactly m nodes and bypass exactly n nodes by rewiring a single pointer. Since every node belongs to exactly one keep or delete segment, and the traversal progresses strictly forward, the final linked list matches the required structure.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

from typing import Optional

class Solution:
    def deleteNodes(self, head: Optional[ListNode], m: int, n: int) -> Optional[ListNode]:
        current = head

        while current:
            # Keep m nodes
            for _ in range(m - 1):
                if current is None:
                    return head
                current = current.next

            # If we reached the end, stop
            if current is None:
                break

            # Delete next n nodes
            temp = current.next

            for _ in range(n):
                if temp is None:
                    break
                temp = temp.next

            # Connect kept part to remaining list
            current.next = temp

            # Move current forward
            current = temp

        return head

The implementation starts by initializing current to the head of the linked list. The outer while loop continues until the traversal reaches the end of the list.

Inside the loop, the first for loop advances current through the m nodes that should remain in the list. We move m - 1 times because current already starts on the first kept node.

After preserving the required nodes, we create a temporary pointer called temp that begins at the first node to delete. The second for loop advances temp by n nodes, effectively skipping the deleted section.

The key operation is:

current.next = temp

This reconnects the preserved portion directly to the remaining list after the deleted nodes.

Finally, current moves to temp so the process can repeat for the next cycle.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteNodes(head *ListNode, m int, n int) *ListNode {
	current := head

	for current != nil {
		// Keep m nodes
		for i := 0; i < m-1; i++ {
			if current == nil {
				return head
			}
			current = current.Next
		}

		// Reached end of list
		if current == nil {
			break
		}

		// Delete next n nodes
		temp := current.Next

		for i := 0; i < n; i++ {
			if temp == nil {
				break
			}
			temp = temp.Next
		}

		// Connect kept nodes to remaining list
		current.Next = temp

		// Move forward
		current = temp
	}

	return head
}

The Go implementation follows the same logic as the Python version. The main difference is explicit pointer handling with nil instead of None.

Since Go uses struct pointers for linked lists, modifying current.Next directly updates the original list in-place. No additional memory allocation is required beyond a few pointer variables.

Integer overflow is not a concern because the constraints are small and the algorithm only performs bounded loop iterations.

Worked Examples

Example 1

Input:

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

Initial list:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13

First Cycle

Keep 2 nodes:

Step	current
Start	1
Move once	2

Delete next 3 nodes:

Deleted Nodes	temp ends at
3, 4, 5	6

Reconnect:

1 -> 2 -> 6

Current list:

1 -> 2 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13

Second Cycle

Keep 2 nodes:

Step	current
Start	6
Move once	7

Delete next 3 nodes:

Deleted Nodes	temp ends at
8, 9, 10	11

Reconnect:

6 -> 7 -> 11

Current list:

1 -> 2 -> 6 -> 7 -> 11 -> 12 -> 13

Third Cycle

Keep 2 nodes:

Step	current
Start	11
Move once	12

Delete next 3 nodes:

Deleted Nodes	temp ends at
13	None

Reconnect:

12 -> None

Final result:

[1,2,6,7,11,12]

Example 2

Input:

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

First Cycle

Keep:

1

Delete:

2, 3, 4

Reconnect:

1 -> 5

Second Cycle

Keep:

5

Delete:

6, 7, 8

Reconnect:

5 -> 9

Third Cycle

Keep:

9

Delete:

10, 11

Final result:

[1,5,9]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited at most once
Space	O(1)	Only a few pointers are used

The algorithm performs a single traversal through the linked list. Even though there are nested loops, the total number of pointer movements across all iterations is bounded by the number of nodes in the list. No auxiliary data structures are created, so the extra memory usage remains constant.

Test Cases

# Helper utilities for testing

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    dummy = ListNode()
    current = dummy

    for value in values:
        current.next = ListNode(value)
        current = current.next

    return dummy.next

def to_list(head):
    result = []

    while head:
        result.append(head.val)
        head = head.next

    return result

class Solution:
    def deleteNodes(self, head, m, n):
        current = head

        while current:
            for _ in range(m - 1):
                if current is None:
                    return head
                current = current.next

            if current is None:
                break

            temp = current.next

            for _ in range(n):
                if temp is None:
                    break
                temp = temp.next

            current.next = temp
            current = temp

        return head

sol = Solution()

# Example 1
head = build_list([1,2,3,4,5,6,7,8,9,10,11,12,13])
assert to_list(sol.deleteNodes(head, 2, 3)) == [1,2,6,7,11,12]  # standard repeating deletion pattern

# Example 2
head = build_list([1,2,3,4,5,6,7,8,9,10,11])
assert to_list(sol.deleteNodes(head, 1, 3)) == [1,5,9]  # keep one, delete three

# Single node list
head = build_list([1])
assert to_list(sol.deleteNodes(head, 1, 1)) == [1]  # deletion phase never starts

# Delete more nodes than remain
head = build_list([1,2,3,4])
assert to_list(sol.deleteNodes(head, 2, 10)) == [1,2]  # deletion reaches end early

# No deletion after final keep block
head = build_list([1,2,3,4,5])
assert to_list(sol.deleteNodes(head, 5, 2)) == [1,2,3,4,5]  # all nodes preserved

# Alternating keep/delete
head = build_list([1,2,3,4,5,6])
assert to_list(sol.deleteNodes(head, 1, 1)) == [1,3,5]  # remove every second node

# Large delete section
head = build_list([1,2,3,4,5,6,7])
assert to_list(sol.deleteNodes(head, 3, 5)) == [1,2,3]  # delete remaining tail

# Exact multiple of pattern
head = build_list([1,2,3,4,5,6,7,8])
assert to_list(sol.deleteNodes(head, 2, 2)) == [1,2,5,6]  # repeated exact cycles

Test Case Summary

Test	Why
[1,2,3,4,5,6,7,8,9,10,11,12,13], m=2, n=3	Validates the standard repeated keep/delete cycle
[1,2,3,4,5,6,7,8,9,10,11], m=1, n=3	Tests minimal keep size
[1], m=1, n=1	Tests single-node boundary case
[1,2,3,4], m=2, n=10	Ensures deletion handles reaching list end
[1,2,3,4,5], m=5, n=2	Tests preserving the entire list
[1,2,3,4,5,6], m=1, n=1	Validates alternating keep/delete behavior
[1,2,3,4,5,6,7], m=3, n=5	Tests deleting the remaining tail
[1,2,3,4,5,6,7,8], m=2, n=2	Tests exact repeating pattern cycles

Edge Cases

One important edge case occurs when the linked list ends during the keep phase. For example, if the list has only three remaining nodes but m = 5, we should simply preserve the rest of the list and stop. A buggy implementation might attempt to continue traversing past the end and dereference a null pointer. The solution prevents this by checking whether current becomes None or nil during traversal.

Another tricky case happens when the deletion phase extends beyond the remaining nodes. Suppose we keep two nodes and must delete ten more, but only three nodes remain. The algorithm handles this naturally because the deletion loop stops once temp becomes None. Reconnecting current.next to None correctly terminates the list.

A third important edge case is when m = 1. In this situation, we preserve exactly one node per cycle and delete the next n nodes. Some implementations incorrectly move one extra step during the keep phase and accidentally skip preserved nodes. Using m - 1 iterations ensures the current node itself counts as the first kept node.

Another subtle case is a single-node linked list. Since there are no nodes after the head, the deletion phase never actually removes anything. The algorithm correctly returns the original head unchanged.