Pseudo-code:

text
length = 0
current = head
while current is not null:
    length++
    current = current.next

target_index = length / 2
current = head
for i from 0 to target_index - 1:
    current = current.next

current.next = current.next.next
return head

Complexity Analysis:

• Time Complexity: $O(N) + O(N/2) \approx O(N)$. While technically linear, this requires traversing the list twice.
• Space Complexity: $O(1)$.
• Why it is suboptimal: In strict system constraints or very large distributed lists, minimizing passes is crucial for performance. The brute force solution works but demonstrates a lack of familiarity with pointer arithmetic patterns.

Core Insight for Delete the Middle Node of a Linked List

The core insight is to use two pointers moving at different speeds to simulate finding the middle without knowing the length n beforehand.

If we have a Slow Pointer moving 1 step at a time and a Fast Pointer moving 2 steps at a time, the Fast Pointer covers distance at twice the rate of the Slow Pointer.

• When the Fast Pointer reaches the end of the list (index n), the Slow Pointer will be exactly at the middle (index n/2).
• Invariant: The distance covered by fast is always $2 \times$ the distance covered by slow.

The Deletion Constraint: To delete a node in a singly linked list, we require access to its predecessor (the node immediately before it). If the Slow Pointer lands directly on the middle node, we cannot easily delete it because we don't have a reference to the previous node.

To solve this, we can modify the initialization. Instead of starting both pointers at head, we can look ahead. Alternatively, we can track a previous pointer. The most elegant modification for this specific problem is to ensure the slow pointer stops one node before the middle. We achieve this by letting the fast pointer lead significantly or by skipping the first step for the slow pointer relative to the fast pointer's check.

Visual Description: Imagine the list as a linear track. We initialize slow at the head and fast two steps ahead (or check two steps ahead). As the algorithm progresses, the fast pointer rapidly approaches the null terminator. The moment fast (or fast.next) hits null, the slow pointer is positioned exactly at the node prior to the one we need to delete. This allows us to perform slow.next = slow.next.next immediately.

Execution Flow

Consider the input head = [1, 3, 4, 7, 1, 2, 6]. Length is 7. Middle node is 7 (index 3).

1. Check Edge Case: List size is > 1. Proceed.
2. Init:
   • slow points to 1 (Index 0).
   • fast points to 4 (Index 2).
3. Iteration 1:
   • fast (Index 2) and fast.next (Index 3) are valid.
   • slow moves to 3 (Index 1).
   • fast moves to 1 (Index 4).
4. Iteration 2:
   • fast (Index 4) and fast.next (Index 5) are valid.
   • slow moves to 4 (Index 2).
   • fast moves to 6 (Index 6).
5. Iteration 3:
   • fast is at Index 6. fast.next is null. Loop terminates.
6. Deletion:
   • slow is at node 4 (Index 2). The middle node is 7 (Index 3).
   • Execute slow.next = slow.next.next.
   • Node 4 now points to 1 (Index 4), skipping 7.
7. Result: [1, 3, 4, 1, 2, 6].

Proof of Correctness

The correctness relies on the arithmetic series of the pointers. Let $N$ be the number of nodes. The fast pointer moves 2 steps for every 1 step of slow. Normally, slow travels $N/2$ steps when fast travels $N$ steps. By initializing fast at index 2 (conceptually head.next.next), we effectively simulate a race where fast has already traveled 2 units. When fast reaches the end ($N$), slow has traveled $(N - 2) / 2 = N/2 - 1$. Index $N/2 - 1$ is exactly the predecessor of the middle node $N/2$. This logic holds for both odd and even lengths due to integer division behavior.

Reference Implementation

C++ Solution for LeetCode 2095

cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        // Edge case: If list has only 1 node, return nullptr
        if (head == nullptr || head->next == nullptr) {
            return nullptr;
        }

        ListNode* slow = head;
        // Start fast two steps ahead to ensure slow stops at the predecessor
        ListNode* fast = head->next->next;

        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }

        // Delete the middle node
        ListNode* toDelete = slow->next;
        slow->next = slow->next->next;
        delete toDelete; // Optional: Free memory in C++

        return head;
    }
};

Java Solution for LeetCode 2095

java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteMiddle(ListNode head) {
        // Edge case: If list has only 1 node, return null
        if (head == null || head.next == null) {
            return null;
        }

        ListNode slow = head;
        // Start fast two steps ahead so slow lands on the node BEFORE middle
        ListNode fast = head.next.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Skip the middle node
        slow.next = slow.next.next;

        return head;
    }
}

Python Solution for LeetCode 2095

python
# 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: Optional[ListNode]) -> Optional[ListNode]:
        # Edge case: If list has only 1 node, return None
        if not head or not head.next:
            return None
        
        slow = head
        # Start fast two steps ahead
        fast = head.next.next
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
        # slow is now at the predecessor of the middle node
        slow.next = slow.next.next
        
        return head

• Mistake: Starting both slow and fast at head without tracking a previous pointer.
• Consequence: slow lands on the middle node. In a singly linked list, you cannot delete a node if you are standing on it (unless you copy values, which is hacky). You need the node before it.