Delete the Middle Node of a Linked List — Modified Fast/Slow Pointer Explained

Problem Statement#

LeetCode 2095 — Delete the Middle Node of a Linked List Difficulty: Medium | Pattern: Fast/Slow Pointers (Modified)

You are given the head of a linked list. Delete the middle node and return the head of the modified linked list. The middle node of a linked list of size n is the floor(n/2)th node (0-indexed).

Constraints:

• Number of nodes: 1 <= n <= 10^5
• 1 <= Node.val <= 10^5

Example 1:

Input:  [1, 3, 4, 7, 1, 2, 6]
Output: [1, 3, 4, 1, 2, 6]
Explanation: n=7, middle = floor(7/2) = 3rd node (0-indexed), value=7. Delete it.

Example 2:

Input:  [1, 2, 3, 4]
Output: [1, 2, 4]
Explanation: n=4, middle = floor(4/2) = 2nd node (0-indexed), value=3. Delete it.

Example 3:

Input:  [2, 1]
Output: [2]
Explanation: n=2, middle = floor(2/2) = 1st node (0-indexed), value=1. Delete it.

Example 4:

Input:  [1]
Output: null
Explanation: Single node is the middle. Delete it.

Why This Problem Matters#

This problem is part of the LeetCode 75 curated study plan and appears regularly in Amazon and Google phone screens. Its significance lies not in complexity — the approach is straightforward — but in the precision required to implement the fast/slow pointer correctly for deletion rather than just identification.

"Find the middle node" (LC 876) and "delete the middle node" differ in one critical way: for deletion, you need access to the node before the middle, not the middle itself. This forces candidates to slightly modify the standard fast/slow pattern — and that modification is where most people make mistakes.

The problem also has an important edge case: a single-node list. The only node IS the middle, and deleting it returns null. Missing this edge case in an interview results in a null pointer dereference and an immediate flag from the interviewer.

Mastering this problem builds the muscle memory for fast/slow pointer manipulation that directly transfers to "Reorder List" (LC 143), "Palindrome Linked List" (LC 234), and "Linked List Cycle II" (LC 142).

The Core Insight#

The classic fast/slow approach for finding the middle starts both pointers at head and stops when fast reaches the last node (or null). The resulting slow is the middle node itself.

For deletion, you need the node before the middle so you can do prev.next = middle.next. The clean trick is to use a dummy head as the starting position for slow:

• slow starts at dummy (one step behind head)
• fast starts at head
• When fast and fast.next are both non-null, advance both

When the loop ends, slow is exactly at the predecessor of the middle node. Then slow.next = slow.next.next deletes the middle in one line.

The dummy head also elegantly handles the single-node edge case: fast is immediately null after the first check fails, and slow is at dummy with slow.next being the only (and middle) node, which gets deleted correctly.

Visual Dry Run#

Input: [1, 3, 4, 7, 1, 2, 6] (n=7, middle at index 3 = node(7))

slow = node(4), slow.next = node(7) (the middle)

slow.next = slow.next.next = node(1) — deletes node(7)

Result: [1, 3, 4, 1, 2, 6]

Edge case: [1]

slow = dummy, slow.next = node(1) (the middle, the only node)

slow.next = slow.next.next = null — deletes node(1)

Result: null (return dummy.next = null)

Solution (Optimal)#

from typing import Optional
 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def deleteMiddle(head: Optional[ListNode]) -> Optional[ListNode]:
    # Edge case: empty list (though constraints say n >= 1)
    if not head:
        return None
 
    # Use dummy head so slow starts one step before the list
    dummy = ListNode(0)
    dummy.next = head
 
    slow = dummy    # will land on predecessor of middle
    fast = head     # moves twice as fast
 
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
 
    # slow.next is the middle node — skip it
    slow.next = slow.next.next
 
    return dummy.next

function deleteMiddle(head) {
    if (!head) return null;
 
    // Dummy head so slow starts one step before the list
    const dummy = { val: 0, next: head };
 
    let slow = dummy;  // predecessor of middle
    let fast = head;
 
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
 
    // Delete the middle node
    slow.next = slow.next.next;
 
    return dummy.next;
}

Complexity:

Common Mistakes#

1. Starting slow at head instead of dummy: If slow starts at head, it lands ON the middle, not the predecessor. You then have no way to delete the middle without an extra prev pointer.
2. Wrong fast/slow initialization: fast must start at head (not dummy) while slow starts at dummy. This creates the exact one-step offset needed.
3. Forgetting the single-node edge case: With a single node, fast.next is null immediately, so the loop never runs. slow remains at dummy, and slow.next.next is null — the delete works correctly. But if you started slow at head, you would crash here.
4. Using while fast.next.next instead of while fast and fast.next: The correct condition stops when fast is at the last node or null, not one step before that.
5. Not handling null return: When the only node is deleted, dummy.next is null. The function must return null (not crash on returning head which was just deleted).

Interview Tips#

• Explain the dummy head motivation: "I start slow at a dummy node so it lands on the predecessor, not the middle itself. This makes deletion a one-liner."
• State the middle index formula: "For n nodes, the middle is at index floor(n/2), 0-indexed. For n=4 that is index 2 (the third node)."
• Walk through both examples: Trace [1, 2, 3, 4] and [1]. The single-node case is where most implementations fail.
• Contrast with LC 876: "LC 876 finds the middle — I just need to find the predecessor. The dummy head trick shifts slow exactly one step back."
• Handle n=1 explicitly if asked: You can add a guard if not head.next: return null, but the dummy approach handles it automatically — mention this.

Follow-up Questions#

1. LeetCode 876 — Middle of Linked List: Find the middle without deleting. Uses the same fast/slow pattern but starts both at head.
2. What if you needed to delete the ceil(n/2) middle? Adjust the fast/slow start positions.
3. Delete all nodes at a given distance from center: Generalize the predecessor-tracking approach.
4. LeetCode 234 — Palindrome Linked List: Uses the same midpoint logic, then reverses the second half.
5. What if the list were doubly linked? The predecessor is available directly via middle.prev — no fast/slow needed.
6. What if you needed to return the deleted node's value? Capture slow.next.val before the deletion.

Key Takeaways#

• Start slow at a dummy head and fast at head. This gives slow a one-step head start so it lands on the predecessor of the middle, enabling O(1) deletion.
• The middle node is at index floor(n/2) (0-indexed). For n=4, that is index 2 — the third node.
• The single-node edge case is handled automatically: the while loop never runs, and slow.next = slow.next.next removes the only node.
• This dummy-head offset trick is reusable any time you need the node before a "found" position in a fast/slow traversal.
• The same fast/slow midpoint logic appears in LC 876, LC 143, LC 234, and LC 142 — master this pattern once and apply it everywhere.
• Time O(n), space O(1) — the expected optimal solution for any linked list traversal problem.