Problem Overview — Delete the Middle Node
LeetCode 2095 asks you to delete the middle node of a singly linked list and return the modified list. The middle is defined as the node at index floor(n/2), using 0-based indexing from the head. For a list of length 7, the middle is at index 3.
For example, given [1,3,4,7,1,2,6] (n=7), the middle is index 3 (value 7). Delete it and return [1,3,4,1,2,6]. For [1,2,3,4] (n=4), the middle is index 2 (value 3) since floor(4/2)=2. For a single-node list [1], the node itself is the middle, so return null.
The constraints make this interesting: the list can have up to 100,000 nodes, so you need an efficient approach. The goal is to do it in one pass without computing the length first.
- n ranges from 1 to 100,000 — efficiency matters
- Middle index is floor(n/2), 0-indexed from head
- Single-node list: delete the head, return null
- The list is singly linked — no backward traversal
Fast/Slow Pointer with Prev Tracking
The classic approach to find the middle of a linked list uses two pointers: slow moves one step at a time while fast moves two steps. When fast reaches the end, slow is at the middle. For deletion, you also need the node before slow — call it prev.
At each iteration, set prev = slow before advancing slow. This gives you the node just before the middle. When the loop ends, prev.next = slow.next skips over the middle node, effectively deleting it from the list.
Using a dummy node (dummy.next = head) before starting lets prev begin at dummy. This is the cleanest way to handle the single-node edge case: if the head itself is the middle, prev is dummy and dummy.next = slow.next = null correctly returns an empty list via dummy.next.
Key Technique
Use a dummy node before head so prev starts at dummy. This handles the single-node case uniformly: when slow=head is the middle, prev=dummy and setting dummy.next = slow.next = null returns an empty list without any special-case code.
Algorithm Steps — Setting Up the Three Pointers
The algorithm uses three pointers — prev, slow, and fast — initialized relative to a dummy sentinel node. The dummy node simplifies deletion at the head without adding conditional branches.
The loop runs while fast and fast.next are both non-null. At each step, prev advances to slow, slow advances one step, and fast advances two steps. When the loop exits, slow is exactly at floor(n/2) — the node to delete.
Performing prev.next = slow.next unlinks the middle node. Returning dummy.next gives the head of the modified list. The entire algorithm runs in O(n) time and O(1) space with a single traversal.
- 1Create dummy node: dummy = ListNode(0); dummy.next = head
- 2Initialize pointers: prev = dummy, slow = head, fast = head
- 3Loop: while fast and fast.next are not null
- 4 Inside loop: prev = slow; slow = slow.next; fast = fast.next.next
- 5After loop: prev.next = slow.next (delete middle)
- 6Return dummy.next
Why the Dummy Node Matters
Without a dummy node, when the list has exactly one node, slow points to head and there is no prev — you cannot bypass the head node. You would need an explicit if-check: "if n == 1, return null". The dummy node eliminates this branching entirely.
With dummy.next = head, prev starts at dummy. If n=1, the while-loop condition (fast and fast.next) fails immediately since fast.next is null. At that point slow=head, and prev.next = slow.next = null. Return dummy.next = null. Correct, no special case needed.
The dummy pattern is a general technique in linked list problems whenever you might need to delete or insert at position 0. It costs one extra node allocation (O(1) space) and saves complexity in your logic.
Alternative Approach
Instead of a dummy node, you can check fast.next and fast.next.next (instead of fast and fast.next) to advance fast one step before the loop. This shifts slow one position earlier so prev is naturally valid. But the dummy node approach handles all edge cases uniformly and is easier to reason about.
Walk-Through Example — [1,3,4,7,1,2,6]
Starting with dummy → 1 → 3 → 4 → 7 → 1 → 2 → 6 → null. prev=dummy, slow=1, fast=1. The list has 7 nodes so the middle is at index 3 (value 7). Three iterations of the loop advance the pointers.
After iteration 1: prev=1, slow=3, fast=4. After iteration 2: prev=3, slow=4, fast=1. After iteration 3: prev=4, slow=7, fast=null (fast.next.next overshot). The loop exits because fast is now null.
At this point slow=7 (the middle), prev=4. Execute prev.next = slow.next: node 4 now points to node 1, skipping node 7. Return dummy.next = 1. Result: [1,3,4,1,2,6]. The deletion is complete in a single traversal.
- 1Start: dummy→1→3→4→7→1→2→6, prev=dummy, slow=1, fast=1
- 2Iter 1: prev=1, slow=3, fast=4
- 3Iter 2: prev=3, slow=4, fast=1
- 4Iter 3: prev=4, slow=7, fast=null (loop exits)
- 5Delete: prev(4).next = slow(7).next = node(1)
- 6Result: [1,3,4,1,2,6]
Code Walkthrough — Python and Java
Both Python and Java implementations follow the same three-pointer structure: create dummy, initialize prev/slow/fast, loop while fast and fast.next are valid, then unlink slow. The time complexity is O(n) and space complexity is O(1) — a single pass with constant extra memory.
In Python: dummy = ListNode(0, head); prev, slow, fast = dummy, head, head. While fast and fast.next: prev = slow; slow = slow.next; fast = fast.next.next. Then prev.next = slow.next; return dummy.next. Six lines for the full solution.
In Java: ListNode dummy = new ListNode(0, head); ListNode prev = dummy, slow = head, fast = head. While (fast != null and fast.next != null): prev = slow; slow = slow.next; fast = fast.next.next. Then prev.next = slow.next; return dummy.next. Same structure, same complexity.
Even-Length Edge Case
For even-length lists, the middle is floor(n/2) — NOT the upper middle. [1,2,3,4] deletes index 2 (value 3), not index 1 (value 2). Verify your fast/slow starting positions: both slow and fast should start at head (not dummy) to get the floor behavior. Starting fast one step ahead shifts the deletion to the upper middle.