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

Удаление среднего узла односвязного списка

Вам необходимо удалить средний узел из односвязного списка. Средним узлом является ⌊n / 2⌋-й узел при использовании 0-индексации.

Вот как это сделать эффективно.

The Strategy

Используйте два указателя, чтобы найти середину за один проход.

• Используйте медленный указатель (slow), который перемещается на один шаг за раз.
• Используйте быстрый указатель (fast), который перемещается на два шага за раз.
• Когда быстрый указатель достигнет конца, медленный указатель будет указывать на средний узел.
• Используйте третий указатель, чтобы отслеживать узел, предшествующий медленному указателю.

The Logic

1. Обработайте граничный случай. Если в списке только один узел, верните null.
2. Инициализируйте медленный и быстрый указатели в начале списка (head).
3. Перемещайте быстрый указатель на два шага, а медленный — на один шаг.
4. Обновляйте указатель prev, чтобы он всегда оставался на один шаг позади медленного указателя.
5. Как только цикл завершится, свяжите узел prev со следующим за slow узлом. Это позволит пропустить средний узел.

Complexity

• Временная сложность: O(n). Вы проходите по списку один раз.
• Пространственная сложность: O(1). Вы используете только три указателя.

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