Problem Description

You have a linked list and need to modify it by keeping some nodes and removing others in a specific pattern. Given the head of the linked list and two integers m and n, you need to:

1. Start at the head of the linked list
2. Keep the first m nodes
3. Remove the next n nodes
4. Repeat steps 2 and 3 until you reach the end of the list

The process works like this: you traverse the linked list, keeping m consecutive nodes, then deleting the next n consecutive nodes, and continue this pattern throughout the entire list. If there are fewer nodes remaining than needed for a complete operation, you process what's available.

For example, if you have a linked list 1→2→3→4→5→6→7→8→9 with m=2 and n=3:

• Keep nodes 1 and 2 (first m=2 nodes)
• Remove nodes 3, 4, and 5 (next n=3 nodes)
• Keep nodes 6 and 7 (next m=2 nodes)
• Remove nodes 8 and 9 (remaining nodes, less than n=3)
• Result: 1→2→6→7

The function should return the head of the modified linked list after performing all the removal operations.

Intuition

The key insight is that we need to traverse the linked list while alternating between two operations: keeping nodes and removing nodes. This suggests a simulation approach where we directly implement what the problem asks.

Think of it like walking through a line of people where you need to keep some and skip others. You'd need two things:

1. A marker to remember where you stopped keeping nodes (so you know where to reconnect after skipping)
2. A way to jump over the nodes you want to remove

The natural approach is to use two pointers:

• A pre pointer that marks the last node we want to keep before we start removing nodes
• A cur pointer that helps us skip over the n nodes we want to remove

The process becomes:

1. Move pre forward by m-1 steps (since pre starts at a node we're keeping, we only need m-1 more steps to keep m total nodes)
2. Use cur to find where we should reconnect after skipping n nodes
3. Connect pre.next to the node after the removed section
4. Move pre to continue the pattern

We need to handle edge cases carefully - what if we run out of nodes while trying to keep m nodes? What if we run out while trying to remove n nodes? The solution handles these by checking if pointers become None and adjusting accordingly.

This simulation approach is straightforward because it directly mirrors the problem statement - we're literally doing what the problem asks us to do, step by step.

Learn more about Linked List patterns.

Solution Approach

The solution uses a simulation approach with two pointers to traverse and modify the linked list in place.

We start by initializing pre to point to the head of the linked list. This pointer will track the last node we keep before each deletion segment.

The main loop continues while pre is not null:

1. Keep m nodes: Starting from the current position of pre, we move forward m-1 times (since pre is already at the first node to keep). During this traversal, we check if pre becomes null - if it does, we've reached the end of the list with fewer than m nodes remaining, so we return the head.

2. Position for deletion: After keeping m nodes, pre now points to the last node we want to keep. We initialize cur to point to pre and then move cur forward n times to skip over the nodes we want to delete.

3. Reconnect the list: After moving cur forward n times:

   • If cur is null, it means we've reached the end while trying to delete nodes, so we set pre.next = None to terminate the list
   • Otherwise, we set pre.next = cur.next to skip over the n nodes and connect to the remaining list

4. Move to next segment: We update pre = pre.next to position it for the next iteration of keeping and removing nodes.

The algorithm handles edge cases naturally:

• If the list has fewer than m nodes from the current position, we return immediately
• If there are fewer than n nodes to delete, we remove whatever remains
• The loop terminates when pre becomes null, meaning we've processed the entire list

Time complexity: O(L) where L is the length of the linked list, as we visit each node at most once. Space complexity: O(1) as we only use a constant amount of extra space for the pointers.

Example Walkthrough

Let's walk through a small example with the linked list 1→2→3→4→5→6 where m=2 and n=1.

Initial State:

head → 1 → 2 → 3 → 4 → 5 → 6 → None
pre →  1

Iteration 1:

1. Keep m=2 nodes: Move pre forward m-1=1 time

   • pre moves from node 1 to node 2

   1 → 2 → 3 → 4 → 5 → 6 → None
       pre

2. Position for deletion: Set cur = pre and move cur forward n=1 time

   • cur starts at node 2, moves to node 3

   1 → 2 → 3 → 4 → 5 → 6 → None
       pre cur

3. Reconnect: Since cur is not null, set pre.next = cur.next

   • pre.next now points to node 4, effectively removing node 3

   1 → 2 ──→ 4 → 5 → 6 → None
       pre   

4. Move forward: pre = pre.next (pre now points to node 4)

   1 → 2 → 4 → 5 → 6 → None
           pre

Iteration 2:

1. Keep m=2 nodes: Move pre forward m-1=1 time

   • pre moves from node 4 to node 5

   1 → 2 → 4 → 5 → 6 → None
               pre

2. Position for deletion: Set cur = pre and move cur forward n=1 time

   • cur starts at node 5, moves to node 6

   1 → 2 → 4 → 5 → 6 → None
               pre cur

3. Reconnect: Since cur is not null, set pre.next = cur.next

   • pre.next now points to None, effectively removing node 6

   1 → 2 → 4 → 5 → None
               pre

4. Move forward: pre = pre.next (pre becomes None)

   • Loop terminates since pre is None

Final Result: 1→2→4→5

The algorithm successfully kept nodes [1,2], removed [3], kept [4,5], and removed [6], following the pattern of keeping 2 and removing 1 throughout the list.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the total number of nodes in the linked list.

The algorithm traverses the linked list once from start to finish. In each iteration:

• It moves m-1 steps to keep m nodes
• Then moves n steps to skip n nodes
• Each node is visited at most once during the entire process

Since we process each node a constant number of times (either keeping it or skipping it), the total time complexity is linear with respect to the number of nodes.

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space:

• Two pointer variables (pre and cur) to track positions in the linked list
• Loop counter variables (implicit in the for loops)

No additional data structures are created that scale with the input size. The modifications are done in-place by adjusting the next pointers of the existing nodes, without creating new nodes or using recursion that would consume stack space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Off-by-One Error When Traversing to Keep Nodes

A common mistake is incorrectly counting the nodes to keep. Since current already points to the first node in the "keep" segment, we should only move forward m-1 times, not m times.

Incorrect approach:

# Wrong: This moves m times, effectively keeping m+1 nodes
for _ in range(m):  # ❌ Wrong!
    if current:
        current = current.next

Correct approach:

# Correct: Move m-1 times since current is already at the first node to keep
for _ in range(m - 1):  # ✓ Correct
    if current:
        current = current.next

Pitfall 2: Not Properly Handling the Deletion Traversal

When deleting nodes, developers often confuse whether to traverse n times or n+1 times. The key is understanding that we need to reach the last node to delete, then connect to the node after it.

Incorrect approach:

# Wrong: This doesn't position correctly for reconnection
node_to_delete = current.next  # Start from next node
for _ in range(n - 1):  # ❌ Traverses one less than needed
    if node_to_delete:
        node_to_delete = node_to_delete.next

Correct approach:

# Correct: Start from current and traverse n times to skip n nodes
node_to_delete = current
for _ in range(n):  # ✓ Traverse exactly n times
    if node_to_delete and node_to_delete.next:
        node_to_delete = node_to_delete.next

Pitfall 3: Forgetting to Handle Edge Cases

Failing to check for null pointers during traversal can cause runtime errors when the list ends mid-operation.

Incorrect approach:

# Wrong: No null checks, will crash if list is shorter
for _ in range(m - 1):
    current = current.next  # ❌ No null check!

# Later in deletion
for _ in range(n):
    node_to_delete = node_to_delete.next  # ❌ No null check!

Correct approach:

# Correct: Always check for null before accessing next
for _ in range(m - 1):
    if current:  # ✓ Null check
        current = current.next

# In deletion
for _ in range(n):
    if node_to_delete and node_to_delete.next:  # ✓ Null check
        node_to_delete = node_to_delete.next

Complete Corrected Solution:

class Solution:
    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:
        current = head
      
        while current:
            # Keep m nodes (move m-1 times)
            for i in range(m - 1):
                if not current:
                    return head
                current = current.next
          
            if not current:
                return head
          
            # Delete n nodes
            temp = current
            for i in range(n):
                if temp and temp.next:
                    temp = temp.next
                else:
                    break
          
            # Reconnect the list
            if temp:
                current.next = temp.next
            else:
                current.next = None
          
            # Move to next segment
            current = current.next
      
        return head