Как работает это решение задачи с LeetCode?

Question

[albertalexandrov]

Есть задача на LeetCode https://leetcode.com/problems/remove-duplicates-fr...:

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Решение у нее такое:

class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return head

        tail = head

        while tail.next:
            current = tail.next

            if current.val == tail.val:
                tail.next = current.next
            else:
                tail = current

        return head

Я понимаю, как tail меняется и зачем это нужно, но как head становится без дублей - не понимаю.

Comments

[igor6130]

Такое ощущение, что здесь только часть кода.

P.S. Хотя head - это же список, а tail является ссылкой на него. Соответственно, все изменения в tail отражаются в head.

[albertalexandrov]

igor6130, решение принимается литкодом

[Сергей П]

igor6130, почему часть? Тут весь код, всё правильно работает и верно написано.

Answer 1

[Сергей П]

Воспринимайте tail и head не в глобальном контексте, а локально. Это всего лишьпеременные с таким именем. Вкаждом конкретном случае и на каждой итерации они могут означать разные места связного списка.

Представьте, что вас много, вы на соревнованиях, у каждого на груди номер и вас выстроили по неубыванию номера в колонну, попросив положить руку на плечо впереди стоящего.
Некоторые номера повторяются и Солюшн Иванович (тренер) идёт вдоль вашей цепочки и делает в точности то, что написано в алгоритме.
При этом там где он идёт, он расцепляет вашу цепочку формируя новую уже без дубликатов.
При этом tail - это хвост новой цепочки, он на каждом шагу новый. Каждому новому хвосту следующим эементом (новым хвостом ставится очередной, но если у него отличный номер. Так тренер выпнет всех с неуникальными номерами из цепочки.

Что конкрено не понятно?

Вот поэкспериментируйте сами:

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

    def __str__(self):
        tail = self.next and f', {self.next}' or ''
        return f'{self.val!r}{tail}'

    def __next__(self):
        if self.next:
            return self.next
        raise StopIteration

    def __iter__(self):
        item = self
        while item:
            yield item.val
            item = item.next

    def copy(self):
        return ListNode(self.val, self.next and self.next.copy())
    
    __repr__ = __str__


 ln=ListNode; l=ln(1, ln(1, ln(2, ln(3, ln(3)))))

Answer 2

[o5a]

Я понимаю, как tail меняется и зачем это нужно, но как head становится без дублей - не понимаю.

tail - последний обработанный (недублирующийся) узел
current - текущий узел
Когда переходим к новому узлу (присваивая его текущему), проверяем, а не совпадает ли он с предыдущим (по значению).
Если совпадает, то текущий узел мы просто выкидываем из цепочки, как бы прицепляя выход предыдущего узла к входу последующего, в обход текущего, за счет:
tail.next = current.next
Таким образом после проверки 2-го узла (повтор значения 1) получится такая картина:

Надеюсь, так понятнее ;)

P.S. а если вопрос именно в том, почему head при этом тоже изменился, то head это просто ссылка на сам список (список = его первый элемент). Мы действиями изменили линковку списка.