82. Remove Duplicates from Sorted List II

public class Solution {
    public ListNode DeleteDuplicates(ListNode head) {
        ListNode sentinel = new ListNode(0, head);
        ListNode 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;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public ListNode DeleteDuplicates(ListNode head) {
        ListNode sentinel = new ListNode(0, head);
        ListNode 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;
    }
}

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode sentinel = new ListNode(0, head);
        ListNode 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;
    }
}

var deleteDuplicates = function (head) {
    let sentinel = new ListNode(0, head);
    let 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;
};

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        sentinel = ListNode(0, head)
        pred = sentinel

        while head:
            if head.next and head.val == head.next.val:
                while head.next and head.val == head.next.val:
                    head = head.next
                pred.next = head.next
            else:
                pred = pred.next
            head = head.next

        return sentinel.next

func deleteDuplicates(head *ListNode) *ListNode {
    sentinel := &ListNode{0, head}
    pred := sentinel
    for head != nil {
        if head.Next != nil && head.Val == head.Next.Val {
            for head.Next != nil && head.Val == head.Next.Val {
                head = head.Next
            }
            pred.Next = head.Next
        } else {
            pred = pred.Next
        }
        head = head.Next
    }
    return sentinel.Next
}

Algorithm

1️⃣

Инициализация "стража" и предшественника:

Создается фиктивный начальный узел sentinel, который указывает на начало связного списка. Это делается для удобства управления указателем на начало списка, особенно если первые несколько узлов могут быть удалены.

Устанавливаем предшественника pred, который будет последним узлом перед потенциально дублирующимися узлами. Изначально предшественником назначается страж.

2️⃣

Проход по списку с проверкой на дубликаты:

Итерируемся по списку начиная с головы head. На каждом шаге проверяем, есть ли дублирующиеся узлы, сравнивая текущий узел head.val с следующим head.next.val.

Если узлы дублируются, то пропускаем все последующие дубликаты, перемещая указатель head до последнего дублированного узла. После этого предшественник pred соединяется с первым узлом после всех дубликатов

pred.next

=

head.next

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

3️⃣

Переход к следующему узлу и возврат результата:

Если текущий узел не имел дубликатов, просто переводим предшественника pred на следующий узел.

Двигаем указатель head на следующий узел в списке.

После завершения цикла возвращаем список, начиная с узла, на который указывает

sentinel.next

, что позволяет исключить все дублирующиеся узлы и вернуть начало нового списка без дубликатов.

😎