Связанные списки — это фундаментальные структуры данных, используемые в информатике и программировании. Удаление узла из связанного списка — обычная операция, но удаление среднего узла может оказаться немного более сложной задачей, чем удаление головного или хвостового узла. В этой статье мы рассмотрим различные методы эффективного удаления среднего узла из связанного списка. Мы предоставим примеры кода на Python для иллюстрации каждого метода.

Метод 1: наивный подход
Самый простой метод — пройти по связанному списку, чтобы найти средний узел, а затем удалить его. Однако этот метод требует двух проходов по связанному списку и имеет временную сложность O(n), где n — длина списка.

def delete_middle_node_naive(head):
    slow = fast = head
    prev = None
    while fast and fast.next:
        fast = fast.next.next
        prev = slow
        slow = slow.next
    prev.next = slow.next
    return head

Метод 2: быстрые и медленные указатели
В этом методе используются два указателя, один из которых движется со скоростью вдвое меньшей, чем другой. Когда быстрый указатель достигнет конца списка, медленный указатель будет указывать на средний узел. Этот метод требует только одного прохода по связанному списку и имеет временную сложность O(n).

def delete_middle_node_fast_slow(head):
    slow = fast = head
    prev = None
    while fast and fast.next:
        fast = fast.next.next
        prev = slow
        slow = slow.next
    prev.next = slow.next
    return head

Метод 3: отслеживание размера
В этом методе мы сначала определяем длину связанного списка, просматривая его один раз. Затем мы вычисляем положение среднего узла и удаляем его. Этот подход требует двух проходов по связанному списку, но гарантирует удаление среднего узла за один проход.

def delete_middle_node_with_size(head):
    current = head
    length = 0
    while current:
        length += 1
        current = current.next
    middle_pos = length // 2
    current = head
    prev = None
    for _ in range(middle_pos):
        prev = current
        current = current.next
    prev.next = current.next
    return head

Метод 4: изменение значений узлов
В этом методе вместо физического удаления среднего узла мы можем изменить его значение на значение следующего узла, а затем пропустить следующий узел. Этот подход не требует каких-либо манипуляций с указателями и имеет временную сложность O(1).

def delete_middle_node_change_values(node):
    if not node or not node.next:
        return False
    next_node = node.next
    node.val = next_node.val
    node.next = next_node.next
    return True

Удалить средний узел из связанного списка можно различными способами. Выбор метода зависит от таких факторов, как временная сложность, использование памяти и необходимость сохранения порядка узлов. Методы, обсуждаемые в этой статье, предлагают различные компромиссы, что позволяет вам выбрать наиболее подходящий для вашего конкретного случая использования.