Delete the Middle Node of a Linked List in One Pass

This one is a Medium-rated classic reported from Amazon, Microsoft, Adobe interviews: "Delete the Middle Node". Like every post in this series, the goal is not memorizing the answer — it is recognizing the Fast and Slow Pointers pattern on sight. Part 9 of 11 in the Fast and Slow Pointers arc.

The Problem

Given the head of a linked list, delete the middle node — index ⌊n / 2⌋ under 0-based indexing — and return the modified head. A list with one node returns None. The wrinkle over finding the middle: deletion needs the node before it.

Input:  1 -> 3 -> 4 -> 7 -> 1 -> 2 -> 6
Output: 1 -> 3 -> 4 -> 1 -> 2 -> 6
Node 7 (index 3 of 7 nodes) is removed.

Recognizing the Fast and Slow Pointers Pattern

Fast and slow pointers (Floyd's tortoise and hare) walk the same structure at different speeds. If there is a cycle they must meet; if there is not, the fast pointer finds the end in half the iterations — which also locates midpoints without knowing the length. It is the default tool for linked lists and for any sequence defined by repeatedly applying a function, all in O(1) space.

Same half-speed invariant as Middle of the Linked List, plus one extra pointer trailing the slow one. Splicing out slow requires prev, and managing that trio cleanly is what the question measures.

The Approach

Walk slow and fast with a prev shadowing slow. When fast exhausts, slow is the middle (⌊n / 2⌋ with the standard loop), and prev.next = slow.next removes it. Guard the single-node list up front.

Alternative offsets exist — starting fast at head.next.next avoids prev entirely by stopping slow one early. Either is fine; committing to one and dry-running a 2-node list is what prevents the classic off-by-one.

Python Solution

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


def delete_middle(head: ListNode | None) -> ListNode | None:
    """Remove the middle node (index n // 2). One pass, O(1) space."""
    if not head or not head.next:
        return None
    prev, slow, fast = None, head, head
    while fast and fast.next:
        prev = slow
        slow = slow.next
        fast = fast.next.next
    prev.next = slow.next
    return head

Complexity

• Time: O(n) — one traversal
• Space: O(1) — three pointers

Interview Tips and Follow-Ups

• Verify the convention: for even lengths this deletes the second middle (index n // 2). Confirm with the interviewer before coding — conventions vary.
• The two-pass version (count then walk to n // 2 − 1) is legitimate; one pass matters when the list arrives as a stream.
• Combine with Remove Nth From End to handle 'delete the k-th from either end' — a small family worth bundling mentally.

More Fast and Slow Pointers problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.