𝗗𝗲𝗹𝗲𝘁𝗲 𝘁𝗵𝗲 𝗠𝗶𝗱𝗱𝗹𝗲 𝗡𝗼𝗱𝗲 𝗼𝗳 𝗮 𝗟𝗶𝗻𝗸𝗲𝗱 𝗟𝗶𝘀𝘁

𝗗𝗲𝗹𝗲𝘁𝗲 𝘁𝗵𝗲 𝗠𝗶𝗱𝗱𝗹𝗲 𝗡𝗼𝗱𝗲 𝗼𝗳 𝗮 𝗟𝗶𝗻𝗸𝗲𝗱 𝗟𝗶𝘀𝘁

You need to remove the middle node from a singly linked list. The middle node is the ⌊n / 2⌋-th node using 0-based indexing.

Here is how you solve it efficiently.

The Strategy

Use two pointers to find the middle in one pass.

• Use a slow pointer that moves one step at a time.
• Use a fast pointer that moves two steps at a time.
• When the fast pointer reaches the end, the slow pointer sits at the middle.
• Keep a third pointer to track the node before the slow pointer.

The Logic

1. Handle the edge case. If the list has only one node, return null.
2. Initialize slow and fast pointers at the head.
3. Move the fast pointer two steps and the slow pointer one step.
4. Update a prev pointer to stay one step behind the slow pointer.
5. Once the loop ends, link the prev node to the node after slow. This skips the middle node.

Complexity

• Time Complexity: O(n). You traverse the list once.
• Space Complexity: O(1). You only use three pointers.

PHP Implementation

function deleteMiddle(ListNode $head): ?ListNode { if ($head->next == null) { return null; }

$slow = $head;
$fast = $head;
$prev = null;

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

$prev->next = $slow->next;

return $head;

}

Source: https://dev.to/mdarifulhaque/2095-delete-the-middle-node-of-a-linked-list-4jf1