Задача: 82. Remove Duplicates from Sorted List II
Сложность: medium

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

Пример:

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

👨‍💻 Алгоритм:

1⃣Инициализация "стража" и предшественника:
Создается фиктивный начальный узел sentinel, который указывает на начало связного списка. Это делается для удобства управления указателем на начало списка, особенно если первые несколько узлов могут быть удалены.
Устанавливаем предшественника pred, который будет последним узлом перед потенциально дублирующимися узлами. Изначально предшественником назначается страж.

2⃣Проход по списку с проверкой на дубликаты:
Итерируемся по списку начиная с головы head. На каждом шаге проверяем, есть ли дублирующиеся узлы, сравнивая текущий узел head.val с следующим head.next.val.
Если узлы дублируются, то пропускаем все последующие дубликаты, перемещая указатель head до последнего дублированного узла. После этого предшественник pred соединяется с первым узлом после всех дубликатов pred.next = head.next, тем самым пропуская весь блок дублированных узлов.

3⃣Переход к следующему узлу и возврат результата:
Если текущий узел не имел дубликатов, просто переводим предшественника pred на следующий узел.
Двигаем указатель head на следующий узел в списке.
После завершения цикла возвращаем список, начиная с узла, на который указывает sentinel.next, что позволяет исключить все дублирующиеся узлы и вернуть начало нового списка без дубликатов.

😎 Решение:

class ListNode {
    public $val = 0;
    public $next = null;

    public function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

function deleteDuplicates($head) {
    $sentinel = new ListNode(0, $head);
    $pred = $sentinel;
    while ($head !== null) {
        if ($head->next !== null && $head->val === $head->next->val) {
            while ($head->next !== null && $head->val === $head->next->val) {
                $head = $head->next;
            }
            $pred->next = $head->next;
        } else {
            $pred = $pred->next;
        }
        $head = $head->next;
    }
    return $sentinel->next;
}
?>

Ставь 👍 и забирай 📚 Базу знаний