L16. Delete the Middle Node of the Linked List

1. Why Do We Need This? (Problem Statement & Status Quo)

In linked list manipulation problems, deleting a node requires more than just finding the target node; it requires access to the preceding node so that its next pointer can be redirected around the deleted element.

Given the head of a singly linked list, our objective is to locate and delete its middle node, then return the updated head. The definition of "middle" depends on whether the total length of the linked list is odd or even:

• Odd Length ($N = 5$): There is exactly one middle node. We eliminate it directly.
• Even Length ($N = 4$): There are two middle nodes (commonly referred to as $M_1$ and $M_2$). By convention, we must delete the second middle node ($M_2$).

2. Core Mental Model & The Predecessor Insight

Real-Life Analogy: Imagine you are standing in a line of people holding hands, and you need to remove the person right in the middle. If you walk straight up to the middle person, you can step out of line, but the person behind them and the person in front of them are left disconnected. To fix the line seamlessly, the person immediately preceding the middle person must reach past them and hold hands with the person directly after them.

Technical Breakdown

If we traverse directly to the middle node:

1. We can inspect its value, but we lack a backward pointer (prev) in a singly linked list to update the preceding node's connection.
2. Therefore, our primary algorithmic goal is not to reach the middle node itself, but rather to reach the node immediately before the middle node.

Once we stand at the node preceding the target, the deletion sequence is trivial:

3. Naive Approach: The Two-Pass Brute Force Solution

The most intuitive way to solve this is a two-pass approach:

1. Pass 1: Traverse the entire linked list from head to null to count the total number of nodes ($N$).
2. Pass 2: Calculate the target position using integer division ($\lfloor N / 2 \rfloor$). Restart from the head and traverse $\lfloor N / 2 \rfloor - 1$ steps to land precisely on the node before the middle node.
3. Link Modification: Re-route pointers and free memory.

Brute Force Pseudo-code

Node* deleteMiddle(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        return nullptr; // Handle edge cases: empty or single-node list
    }
    
    Node* temp = head;
    int n = 0;
    
    // Pass 1: Find total length N
    while (temp != nullptr) {
        n++;
        temp = temp->next;
    }
    
    int resultant = n / 2; // Floor division for position
    temp = head;
    
    // Pass 2: Traverse to the node before the middle
    while (temp != nullptr) {
        resultant--;
        if (resultant == 0) {
            break;
        }
        temp = temp->next;
    }
    
    // Re-link and delete
    Node* middle = temp->next;
    temp->next = temp->next->next;
    delete middle; // C++ memory deallocation
    
    return head;
}

Complexity Analysis

• Time Complexity: $O(N + N/2) \approx O(N)$ because we traverse the list twice.
• Space Complexity: $O(1)$ auxiliary space.

4. The Interviewer's Objection & Optimization Goal

While the two-pass brute force solution is functionally correct, an experienced interviewer will flag the redundant traversal.

• The Critique: "You are traversing the linked list twice. Can you achieve this in a single pass?"
• The Solution: We must adapt the Tortoise and Hare Algorithm (Fast and Slow pointers) to land one step short of the middle node on a single traversal.

5. Optimal Approach: One-Pass Tortoise and Hare Evolution

In standard middle-finding algorithms:

• Slow pointer moves by $1$ step (slow = slow->next).
• Fast pointer moves by $2$ steps (fast = fast->next->next).

To make slow land on the node before the middle instead of the middle itself, we introduce a head start / offset strategy:

1. Advance the fast pointer by two steps before the loop starts, while keeping slow at the head.
2. Alternatively, skip the first movement step of slow so that slow lags behind by exactly one node throughout the traversal.

Walkthrough: Odd vs. Even Length

6. Optimal Code Implementation

Here is the complete, production-ready implementation incorporating the tortoise-and-hare offset adjustment and memory management:

/**
 * 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 1: Empty list or single-node list
        if (head == nullptr || head->next == nullptr) {
            delete head;
            return nullptr;
        }
        
        ListNode* slow = head;
        ListNode* fast = head;
        
        // Give fast a head start of 2 steps to offset slow's final landing spot
        fast = fast->next->next;
        
        // Traverse simultaneously until fast reaches the end (odd) or null (even)
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // 'slow' is now at the node BEFORE the middle node
        ListNode* middle = slow->next;
        slow->next = slow->next->next;
        
        // Free memory (language-dependent, e.g., C++)
        delete middle;
        
        return head;
    }
};

7. Real-World Practical Pitfalls & Edge Cases

When writing production-grade linked list code, always test against these boundary conditions to prevent segmentation faults:

1. Empty List (head == nullptr):
   • Behavior: Attempting to access head->next directly causes a null pointer dereference.
   • Fix: Guard the function at the very beginning by checking if (head == nullptr) return nullptr;.
2. Single-Node List (head->next == nullptr):
   • Behavior: Deleting the middle of a 1-element list leaves an empty list. If fast starts with head->next->next, it will crash dereferencing a null pointer.
   • Fix: Explicitly check if (head->next == nullptr) and return nullptr after freeing the head.
3. Two-Node List (head->next->next == nullptr):
   • Behavior: Length is 2 (even). Middle nodes are $M_1$ (node 1) and $M_2$ (node 2). We must delete $M_2$, meaning the head remains and its next becomes null.
   • Handling: Handled seamlessly by the optimal loop condition since fast jumps to null on the initial offset, bypassing the while loop and correctly updating slow (node 1) to point to null.

8. Summary and Key Takeaways

• The Core Objective: Deleting a node in a singly linked list requires accessing the preceding node, not just the target node itself.
• Length Dependency: For odd lengths, there is one middle node; for even lengths, the problem requires deleting the second middle node ($M_2$).
• Brute Force Limitation: Counting total nodes in Pass 1 and traversing to $\lfloor N/2 \rfloor$ in Pass 2 results in an unnecessary two-pass solution.
• The Optimal Pattern: The Tortoise and Hare Algorithm can be optimized into a one-pass solution by giving the fast pointer an initial two-step head start.
• Offset Landing: Shifting fast ahead initially forces the slow pointer to halt exactly one node before the middle node.
• Memory Safety: Always remember to deallocate/free removed nodes in languages like C++ to prevent memory leaks.
• Time & Space Complexity: The optimal solution runs in $O(N)$ time and $O(1)$ auxiliary space.