Delete N Nodes After M Nodes of a Linked List

Easy

Microsoft

2 views

Topics:

Linked Lists

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 at the current node.
Remove the next n nodes, starting at the m + 1 node.
Continue with the node immediately after the removed nodes as the new current node.
Repeat steps 2 and 3 until you reach the end of the list.

Return the head of the modified list.

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 2 nodes, delete the next 3 nodes. 
Repeat until the end of the list.

Example 2:

Input: head = [1,2,3,4,5,6,7,8,9,10,11], m = 1, n = 3
Output: [1,5,9]
Explanation: Keep the first 1 node, delete the next 3 nodes. 
Repeat until the end of the list.

Example 3:

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

Constraints:

The number of nodes in the list is in the range [1, 10⁴].
1 <= m, n <= 1000

Delete N Nodes After M Nodes of a Linked List

Easy

Microsoft

2 views

Topics:

Linked Lists

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 at the current node.
Remove the next n nodes, starting at the m + 1 node.
Continue with the node immediately after the removed nodes as the new current node.
Repeat steps 2 and 3 until you reach the end of the list.

Return the head of the modified list.

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 2 nodes, delete the next 3 nodes. 
Repeat until the end of the list.

Example 2:

Input: head = [1,2,3,4,5,6,7,8,9,10,11], m = 1, n = 3
Output: [1,5,9]
Explanation: Keep the first 1 node, delete the next 3 nodes. 
Repeat until the end of the list.

Example 3:

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

Constraints:

The number of nodes in the list is in the range [1, 10⁴].
1 <= m, n <= 1000

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on m and n? Can they be zero, negative, or larger than the length of the linked list?
Can the linked list be empty, and if so, what should I return?
What is the data type of the values stored in the linked list nodes (e.g., integer, string)?
Should the original linked list be modified in place, or am I allowed to create a new linked list?
If `m + n` is greater than the remaining nodes in the list, how should I handle the remaining nodes (retain the m and drop the rest, or is there another specific behavior expected)?

Brute Force Solution

Approach

The brute force method to solve this list manipulation challenge involves going through the list, keeping some items and removing others, based on the given numbers. We'll walk through the list and perform deletions according to the rules.

Here's how the algorithm would work step-by-step:

Start at the beginning of the list.
Keep the first set of items as they are.
Then, remove the next set of items.
After removing, again keep the next set of items.
Repeat the process of keeping some and deleting some, going further down the list until you reach the end.
Once finished, you'll have a modified list based on keeping and deleting as per the provided instructions.

Code Implementation

def delete_n_nodes_after_m_nodes(head, m_value, n_value):    current_node = head

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

        # If we reached the end of the list
        if current_node is None:
            return head

        next_node = current_node.next

        # Delete n nodes
        for _ in range(n_value):
            if next_node is None:
                break
            next_node = next_node.next

        # Connect the m nodes to the node after the n deleted nodes
        # This effectively removes the n nodes
        current_node.next = next_node

        # Advance current_node to the new next node to continue the process
        current_node = next_node

    return head

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the linked list once. In each iteration, it either skips M nodes or deletes N nodes. Both skipping and deleting take constant time per node. Therefore, the time complexity is directly proportional to the number of nodes in the list, which is 'n'. Thus, the overall time complexity is O(n).

Space Complexity

O(1) – The provided plain English explanation describes an iterative process of traversing the linked list, keeping and deleting nodes in place. No additional data structures like arrays, hashmaps, or temporary lists are created to store intermediate results or node references. The algorithm modifies the existing linked list directly. Therefore, the space complexity is constant, independent of the input list size N.

Optimal Solution

Approach

The efficient way to solve this linked list problem is to walk through the list and strategically skip nodes. We'll use two counters to keep track of which nodes to keep and which to skip.

Here's how the algorithm would work step-by-step:

Start at the beginning of the list.
Count forward a specific number of nodes (let's call this 'M'). These are the nodes we want to keep.
Once we've counted 'M' nodes, then begin counting again, but this time, we're counting the nodes we want to delete (let's call this 'N').
After counting 'N' nodes to delete, skip over those 'N' nodes by connecting the 'M'th node directly to the node after the 'N' skipped nodes.
Repeat the process of counting 'M' nodes to keep and then 'N' nodes to skip (delete) until you reach the end of the list.
If you reach the end of the list early, simply stop the process when there are no more nodes to process.

Code Implementation

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

def delete_n_nodes_after_m_nodes(head, number_of_nodes_to_keep, number_of_nodes_to_delete):
    current_node = head

    while current_node:
        # Traverse M nodes
        for _ in range(number_of_nodes_to_keep - 1):
            if current_node is None:
                return head
            current_node = current_node.next

        # If we reach the end, no more nodes to delete
        if current_node is None:
            return head

        next_node = current_node.next

        # Delete N nodes
        for _ in range(number_of_nodes_to_delete):
            if next_node is None:
                break
            next_node = next_node.next

        # Link the kept nodes to the node after the deleted nodes
        current_node.next = next_node

        current_node = next_node

    return head

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the linked list once. For a linked list of size 'n', it visits each node to determine whether to keep it (counting M nodes) or delete it (skipping N nodes). Both the counting and skipping operations take constant time O(1) per node. Therefore, the total time complexity is directly proportional to the number of nodes, resulting in O(n).

Space Complexity

O(1) – The algorithm iterates through the linked list and modifies it in place. It primarily uses a few integer variables, such as counters for 'M' and 'N', and pointers to traverse and update the linked list structure. No auxiliary data structures that scale with the input size (N, the number of nodes in the linked list) are created. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
head is null	Return null immediately as there is no list to process.
m is 0	Delete every node from head to tail and return null.
n is 0	Return the original head because we keep all nodes.
m is larger than the length of the list	Keep the entire list since there aren't enough nodes to delete after m nodes; simply return the original head.
n is larger than the remaining list length after m nodes	Delete all remaining nodes after retaining m nodes.
m and n are large, leading to potential integer overflow if summed repeatedly	The loop condition should only depend on list traversal, avoiding calculations with potentially overflowing values.
List length is very large, potentially impacting performance	The iterative approach is used to ensure linear time complexity O(N) and avoid stack overflow issues from recursion with long lists.
Both m and n are extremely large and close to the maximum integer value	The code will still execute correctly as long as individual m and n calculations stay within valid integer ranges during traversal, it does not matter that their sum is invalid.