2095. Delete the Middle Node of a Linked List

LeetCode задача 2095

Задача

Дан связный список (linked list). Задача — удалить средний узел из этого списка и вернуть начало(head) измененного списка.

Подсказки

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

Подход

1. Используем два указателя для прохода по списку: один медленный и один быстрый. Оба начинают с головного узла списка.
2. Быстрый указатель будет двигаться в два раза быстрее медленного. Каждый шаг он перескакивает через два узла, в то время как медленный только на один. Таким образом, когда быстрый указатель достигнет конца список, первый указатель будет на середине.
3. По мере продвижения указателей сохраняем узел, предшествующий медленному поинтеру (prev), так как именно его next нам нужно будет изменить.
4. Когда быстрый указатель достигнет конца списка или окажется на последнем узле, медленный указатель будет указывать на средний узел.
5. Удаляем средний узел.

Алгоритм

1. Инициализируем два указателя: один медленный (p1), другой быстрый (p2), и третий указатель prev.
2. Обновляем указатели до момента достижения быстрым конца списка:
   • Быстрый указатель на каждом шаге перепрыгивает через next.
   • Временный (prev) указатель сохраняет ссылку на медленный указатель до его изменения
   • Медленный указатель на каждом шаге обновляется до next.
3. Удаляем средний элемент путем обновления ссылки в указателе prev.next на p1.next

Решение

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def deleteMiddleNode(head: ListNode) -> ListNode:
        if not head.next:
            return None

        p1 = head  # быстрый
        p2 = head  # медленный
        prev = None  # предыдущий. Будет в середине

        while p2 and p2.next:
            prev = p1
            p1 = p1.next
            p2 = p2.next.next

        prev.next = p1.next

        return head