Delete the Middle Node of a Linked List

Intuitionfinding the node and its predecessor in one pass

Deleting a node from a singly linked list requires more than locating that node: you must also reach the node before it, because only the predecessor can change its next pointer. Once you have both, deletion is one link change: make the predecessor skip the middle node and point directly to the node after it.

The middle is defined by position, so two pointers let you discover it without counting first. Move fast by two nodes for every one node slow moves. When fast reaches the end, slow is at the required middle for both odd and even lengths, provided you remember the node slow occupied just before its final move.

Approach

1. 1Handle a one-node list immediately by returning nullptr, because its only node is the middle and there is no predecessor whose link can be updated.
2. 2Start slow and fast at head and set prev to nullptr, because slow must begin at index 0 while prev records the node behind it after each move.
3. 3While fast and fast->next both exist, save prev as slow, advance slow once, and advance fast twice, because this keeps the pointers at a fixed one-to-two speed ratio without reading through a null link.
4. 4When the loop ends, slow is the node at index floor(n / 2), and prev is its predecessor; stopping on the same condition for odd and even lengths gives index 1 for length 2 and index 2 for length 4.
5. 5Set prev->next to slow->next, because bypassing slow removes it from the chain while preserving every node before and after it.
6. 6Delete slow and return head, because the node is no longer reachable and the original head remains unchanged for every list with at least two nodes.

Complexityone scan and constant working memory

Annotated solutionC++ · one-pass two-pointer solution

#include <cstddef>

using namespace std;

class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return nullptr;
        }

        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* prev = nullptr;

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

        prev->next = slow->next;
        delete slow;
        return head;
    }
};

The order inside the loop is important. Save prev before moving slow, otherwise you lose the only pointer to the node whose next link must change. The initial one-node guard is also part of the algorithm rather than a convenience: without it, prev remains null and the deletion line cannot be applied to the head node.

The counting alternativea different arrangement, not an optimisation

You can first count the nodes, compute middle index n / 2, and then walk to that index while keeping its predecessor. This uses the same O(n) time and O(1) extra space, but it makes two passes instead of letting two speeds determine the position in one pass. It can be easier to reason about when the index itself is useful, but the fast-slow version is usually shorter.

#include <cstddef>

using namespace std;

class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return nullptr;
        }

        int length = 0;
        for (ListNode* node = head; node != nullptr; node = node->next) {
            ++length;
        }

        ListNode* prev = nullptr;
        ListNode* middle = head;
        for (int index = 0; index < length / 2; ++index) {
            prev = middle;
            middle = middle->next;
        }

        prev->next = middle->next;
        delete middle;
        return head;
    }
};

Common mistakesthe two boundary conditions that change the answer