Delete the Middle Node of a Linked List: Fast and Slow Pointers

Delete the Middle Node of a Linked List is LeetCode problem 2095. You are given a linked list and need to remove its middle node in a single pass. The trick is to use the fast and slow pointer technique so you never have to count the total length first.

The problem

Given the head of a linked list, delete the middle node and return the head of the modified list. The middle node is defined as the node at index floor(n / 2) where n is the number of nodes (0-indexed). For an even-length list, this means you delete the second of the two middle nodes.

Example: head = [1, 3, 4, 7, 1, 2, 6], output = [1, 3, 4, 1, 2, 6]. The list has 7 nodes, so the middle is at index floor(7 / 2) = 3, which is the node with value 7.

Why this is a linked list traversal problem

If this were an array, you would compute the middle index with len(arr) // 2 and remove the element in O(1) lookup time. But a linked list has no random access. You cannot jump to index 3 directly. You have to walk there node by node.

The naive approach uses two passes. First, traverse the entire list to count n. Then, traverse again to node n/2 - 1 and rewire its next pointer to skip the middle. This works, but it requires two full traversals.

The optimal approach uses one pass. By running a fast pointer at double speed alongside a slow pointer, you find the middle without ever counting. When fast reaches the end, slow is sitting at (or just before) the middle node.

The approach: fast and slow pointers

The idea is simple. Set up two pointers: slow moves one step at a time, and fast moves two steps at a time. Since fast covers the list at double speed, slow will have covered exactly half the list when fast reaches the end.

The one subtlety is deletion. To delete a node from a singly linked list, you need a reference to the node before it so you can set prev.next = target.next. There are two ways to handle this:

1. Keep a separate prev pointer that trails one step behind slow.
2. Initialize fast two steps ahead so that slow naturally stops one node before the middle.

The second approach is cleaner. By starting fast at head.next.next instead of head, slow ends up one position earlier. When the loop finishes, slow.next is the middle node, and you delete it with slow.next = slow.next.next.

Visual walkthrough

The walkthrough traces through [1, 3, 4, 7, 1, 2, 6] using a prev pointer to track the node before slow. After three iterations, fast reaches the last node and the loop stops. At that point, slow is at the middle (node 7), and prev.next = slow.next bypasses it. The resulting list is [1, 3, 4, 1, 2, 6].

The solution

def deleteMiddle(head):
    if not head.next:
        return None

    slow = head
    fast = head.next.next

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

    slow.next = slow.next.next
    return head

Here is the breakdown:

1. Edge case. If the list has only one node, head.next is None. There is no middle to keep, so return None.
2. Initialize. slow starts at head. fast starts at head.next.next, which is two steps ahead. This offset is the key to the whole approach.
3. Loop. While fast and fast.next are both non-null, advance slow by one step and fast by two steps. The standard guard while fast and fast.next handles both odd and even length lists.
4. Delete. When the loop exits, slow is the node right before the middle. Set slow.next = slow.next.next to skip over the middle node.
5. Return. The head never changes (since the middle node is never the first node when there are at least 2 nodes), so return head.

Complexity analysis

The building blocks

Fast and slow pointers (tortoise and hare)

When a fast pointer moves at 2x speed and a slow pointer moves at 1x speed through a linked list, slow ends up at the midpoint when fast reaches the end. This works because slow covers exactly half the distance that fast covers. If the list has n nodes, fast takes roughly n/2 iterations to reach the end, and slow has moved n/2 nodes forward in that time.

This pattern has three classic applications:

• Finding the middle of a linked list (LeetCode 876). The foundation for this problem.
• Cycle detection using Floyd's algorithm (LeetCode 141). If there is a cycle, fast and slow will eventually collide inside it.
• Finding the cycle start (LeetCode 142). After detection, reset one pointer to the head and advance both at the same speed. They meet at the cycle entry.

The key difference in this problem is the initialization. By starting fast two steps ahead, you shift where slow lands by one position, which lets you perform the deletion without a separate prev pointer.

Edge cases

• Single node list. Return None since there is nothing left after deleting the only node.
• Two node list. Delete the second node (index 1). fast starts at head.next.next which is None, so the loop never runs. slow.next = slow.next.next sets head.next to None. Return head with just one node.
• Even length list. The middle is the second of the two middle nodes, at index floor(n/2). For a 4-node list [1, 2, 3, 4], you delete index 2 (value 3).
• Odd length list. The middle is the exact center node. For a 5-node list [1, 2, 3, 4, 5], you delete index 2 (value 3).

From understanding to recall

The tricky part of this solution is the initialization. Starting fast at head.next.next instead of head is the difference between slow landing on the middle node and slow landing one node before it. If you get that wrong, your deletion logic breaks.

The loop body itself is identical to the standard tortoise and hare pattern. The only thing you need to memorize beyond the basics is that two-step head start for fast. Practice typing it from scratch a few times, and pay attention to that initialization line. After a few reps, the head.next.next start becomes second nature.

Related posts

• Linked List Cycle - Floyd's cycle detection algorithm, the classic fast/slow pointer technique
• Middle of the Linked List - Finding the middle node without deletion, the foundation for this problem
• Remove Nth Node From End of List - Another linked list deletion using a two-pointer offset technique