2095. Delete the Middle Node of a Linked List

Medium · solved 2026-10-05 · Open on LeetCode

linked-listtwo-pointers

Time O(n) · Space O(1)

How to get there

Stop one node before the middle

1. Find what a deletion needs. A singly linked list removes a node by rewiring the node before it: before.next = before.next.next. The middle is at index n // 2, so the walk has to stop at index n // 2 − 1.

2. Walk it by hand and find where one pass gets stuck. On [1, 3, 4, 7, 1, 2, 6], n = 7, so the middle is index 3, the 7, and the walk must stop at index 2, the 4. But n is known only at the end of the list, and by then index 2 is behind, with no way back. Counting first and walking again takes two passes.

3. Find what to remember instead. The middle of the nodes seen so far. After k nodes it sits at index k // 2, so it moves one step for every two nodes the walk covers. When the walk reaches the end, that pointer is at the middle of the whole list.

4. Let two speeds do the counting. “One step for every two” is two pointers: fast moves two nodes per turn and slow one. Starting fast two nodes ahead keeps slow one node behind the middle, which is exactly where step 1 needs it.

5. Handle the list with no node before the middle. With one node, the middle is the head itself, and deleting it leaves an empty list: return None. Every longer list has a node before its middle.

6. Check the cost. One pass of about n/2 turns, and two pointers: O(n) time, O(1) space.

The reusable recipe: to reach a fixed fraction of a list’s length in one pass, move two pointers at speeds in that ratio. To delete a node, stop on the one before it.

Let the pointers' meanings write the loop

Variable	Always means, at the top of the loop, after i turns
`slow`	the node at index i
`fast`	the node at index 2i + 2, or `None` once that index is past the end

Code	What happened	What it keeps true
`if not head.next: return None`	the list has one node, which is the middle	the empty list is the answer, and `head.next.next` below is safe
`slow, fast = head, head.next.next`	no turns yet, i = 0	`slow` at index 0, `fast` at index 2
`while fast and fast.next:`	both index 2i + 2 and 2i + 3 exist	there is room for `fast` to move two nodes
`slow = slow.next`, `fast = fast.next.next`	one more turn, i grows by 1	`slow` gains 1 and `fast` gains 2
`slow.next = slow.next.next`	the loop stopped	`slow` is right before the middle, so this unlinks it

Where the loop stops depends on whether n is even or odd:

n	`fast` stops at	`slow` stops at
even	index n, which is `None`	index n/2 − 1
odd	index n − 1, the last node	index (n − 3)/2

Both are n // 2 − 1, the node before the middle.

The method carries over: write down where each pointer always is, make each turn the smallest move that keeps it there, then solve the stop condition for the index you need.

Alternatives compared

Approach	Time	Space	How it works
Copy the nodes into a list	O(n)	O(n)	Store every node in an array, then set `nodes[n // 2 - 1].next = nodes[n // 2].next`.
Count, then walk again	O(n), two passes	O(1)	The first pass finds n; the second stops at index n // 2 − 1.
One cursor, move the middle every other node (`solution-1-original.py`)	O(n)	O(1)	`cursor` visits every node, and a parity counter moves `mid_cursor` on every second one, with `prev_cursor` one behind it.
Fast and slow pointers (chosen, `solution-2-clean.py`)	O(n)	O(1)	`fast` moves two nodes per turn and `slow` one, starting two apart, so `slow` stops on the node before the middle.

The last two make the same single pass. On a 100,000-node list in CPython, measured on one machine, the original took 12.0 ms and fast and slow took 2.3 ms. The original runs n turns with a modulo and a counter in each, while fast and slow runs n/2 turns of two pointer moves.

solution-1-original.py

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteMiddle(self, head: ListNode | None) -> ListNode | None:
        # mid_cursor, cursor
        # 0, 0: skip -> 0, 0
        # 0, 1: move -> 1, 1
        # 1, 2: skip -> 1, 2
        # 1, 3: move -> 2, 3
        # 2, 4: skip -> 2, 4
        # 2, 5: move -> 3, 5
        cursor, counter, mid_index, prev_cursor, mid_cursor = head, 0, 0, head, head

        if not head.next:
            return None

        while cursor:
            if counter % 2 != 0:
                mid_index += 1
                prev_cursor = mid_cursor
                mid_cursor = mid_cursor.next
            counter += 1
            cursor = cursor.next

        prev_cursor.next = mid_cursor.next

        return head

solution-2-clean.py

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteMiddle(self, head: ListNode | None) -> ListNode | None:
        if not head.next:
            return None

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

        slow.next = slow.next.next
        return head

Notes

Write your approach, insights, and mistakes here. Any other file in this folder (e.g. solution.py, attempt-1.py) is rendered below as code.