Problem Description

You are given the head of a linked list. Your task is to delete the middle node and return the head of the modified linked list.

The middle node is defined using 0-based indexing as the node at position ⌊n/2⌋, where n is the total number of nodes in the linked list and ⌊x⌋ represents the floor function (largest integer less than or equal to x).

For example:

• If the list has 1 node (n=1): the middle node is at index 0 (the only node)
• If the list has 2 nodes (n=2): the middle node is at index 1 (the second node)
• If the list has 3 nodes (n=3): the middle node is at index 1 (the second node)
• If the list has 4 nodes (n=4): the middle node is at index 2 (the third node)
• If the list has 5 nodes (n=5): the middle node is at index 2 (the third node)

The solution uses the fast and slow pointer technique. A dummy node is created that points to the head, with slow starting at the dummy node and fast starting at the head. The fast pointer moves twice as fast as the slow pointer. When fast reaches the end of the list, slow will be positioned right before the middle node. The middle node is then deleted by updating slow.next to skip over it (slow.next = slow.next.next). Finally, dummy.next is returned as the new head of the modified list.

Intuition

The key insight is that we need to find and remove the middle node in a single pass through the linked list. Since we can't directly access nodes by index in a linked list, we need a clever way to locate the middle position.

The fast and slow pointer technique naturally solves this problem. If we have two pointers where one moves twice as fast as the other, when the fast pointer reaches the end, the slow pointer will be at the halfway point. Think of it like two runners on a track - if one runs at double the speed, when the faster runner completes the full lap, the slower runner will have completed exactly half a lap.

However, there's a subtle challenge: we don't just need to find the middle node, we need to delete it. To delete a node in a linked list, we need access to the node before it so we can update its next pointer to skip the middle node.

This is why the solution cleverly starts the slow pointer one step behind by placing it at a dummy node that points to the head, while fast starts at the actual head. This offset ensures that when fast reaches the end, slow is positioned exactly one node before the middle node - the perfect position to perform the deletion.

The beauty of this approach is that it handles all edge cases naturally. Whether the list has an odd or even number of nodes, the ⌊n/2⌋ calculation is implicitly handled by the pointer movement pattern. The dummy node also elegantly handles the case where we might need to delete the first node of the list.

Learn more about Linked List and Two Pointers patterns.

Solution Approach

The implementation uses the fast and slow pointer technique with a clever initialization to position the pointers correctly for deletion.

Step 1: Initialize the pointers

dummy = ListNode(next=head)
slow, fast = dummy, head

We create a dummy node that points to the head of the list. The slow pointer starts at the dummy node (one position before the head), while the fast pointer starts at the head. This offset is crucial - it ensures that when we find the middle, slow will be positioned right before it.

Step 2: Move the pointers

while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

We move both pointers through the list:

• slow moves one step at a time
• fast moves two steps at a time

The loop continues while fast is not null and fast.next is not null. This condition handles both odd and even length lists:

• For even-length lists: fast will become null
• For odd-length lists: fast.next will become null

When this loop ends, slow is positioned exactly one node before the middle node we want to delete.

Step 3: Delete the middle node

slow.next = slow.next.next

Since slow is positioned before the middle node, slow.next is the middle node itself. We skip over it by setting slow.next to point to slow.next.next, effectively removing the middle node from the list.

Step 4: Return the modified list

return dummy.next

We return dummy.next, which is the head of the modified list. Using the dummy node ensures this works even if the original list had only one node (in which case we'd be deleting the head itself, and dummy.next would now be null).

The time complexity is O(n) as we traverse the list once, and the space complexity is O(1) as we only use a constant amount of extra space for the pointers.

Example Walkthrough

Let's walk through a concrete example with the linked list: 1 -> 2 -> 3 -> 4 -> 5

We need to delete the middle node. With n=5 nodes, the middle node is at index ⌊5/2⌋ = 2, which is the node with value 3.

Initial Setup:

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
  ↑      ↑
 slow   fast

We create a dummy node pointing to head (1). The slow pointer starts at dummy, and fast starts at the head (1).

First Iteration:

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
         ↑         ↑
        slow      fast

• slow moves one step: dummy → 1
• fast moves two steps: 1 → 2 → 3
• Condition check: fast (3) exists and fast.next (4) exists ✓

Second Iteration:

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
              ↑              ↑
             slow           fast

• slow moves one step: 1 → 2
• fast moves two steps: 3 → 4 → 5
• Condition check: fast (5) exists but fast.next is null ✗

Loop Ends - Delete the Middle Node:

Now slow is at node 2, which is exactly one position before the middle node (3).

Before deletion:
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
              ↑
             slow
           
slow.next = slow.next.next (skip node 3)

After deletion:
dummy -> 1 -> 2 --------> 4 -> 5 -> null
              ↑
             slow

Return Result: Return dummy.next, which gives us the head of the modified list: 1 -> 2 -> 4 -> 5

The middle node (3) has been successfully removed from the list.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the linked list. This is because the algorithm uses the two-pointer technique (slow and fast pointers) to traverse the list. The fast pointer moves twice as fast as the slow pointer, reaching the end of the list after approximately n/2 iterations. Since the slow pointer also moves n/2 times, the total number of operations is proportional to n.

The space complexity is O(1). The algorithm only uses a constant amount of extra space regardless of the input size. It creates a dummy node and uses two pointer variables (slow and fast), which require fixed memory allocation that doesn't scale with the size of the input linked list.

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

Common Pitfalls

1. Incorrect Pointer Initialization

A common mistake is initializing both slow and fast pointers at the same starting position (both at head or both at dummy). This leads to incorrect positioning when the loop ends.

Incorrect approach:

# Wrong: Both pointers start at head
slow = head
fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
# Now slow points to the middle node, not the node before it!

Why this fails: When both pointers start at the same position, slow ends up pointing to the middle node itself rather than the node before it. You then cannot delete the middle node properly since you need access to the previous node to update its next pointer.

Solution: Always maintain the offset by starting slow at dummy and fast at head:

dummy = ListNode(next=head)
slow = dummy  # Starts one position behind
fast = head   # Starts at head

2. Not Handling Single-Node Lists

Without a dummy node, deleting the only node in a single-node list becomes problematic.

Incorrect approach:

# Wrong: No dummy node
if not head or not head.next:
    return None  # Special case handling
slow = head
fast = head.next
# ... rest of the logic

Why this fails: This requires special case handling for single-node lists, making the code more complex and error-prone. You need to remember to check for this edge case explicitly.

Solution: Using a dummy node elegantly handles all cases including single-node lists:

dummy = ListNode(next=head)
# No special cases needed - the algorithm handles n=1 naturally

3. Incorrect Loop Condition

Using only while fast.next and fast.next.next can cause issues.

Incorrect approach:

# Wrong: Checking fast.next.next in the condition
while fast.next and fast.next.next:
    slow = slow.next
    fast = fast.next.next

Why this fails: This condition stops the loop too early for certain list lengths. For example, with a 2-node list, the loop wouldn't execute at all, leaving slow at the dummy node when it should move once.

Solution: Use the simpler and correct condition:

while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

This ensures the loop runs the correct number of times for all list lengths.