Задача – удалить узлы, значения которых фигурируют в списке более одного раза

Just Xor

Вот что можно сделать для решения этой проблемы: мы можем не только полагаться на флаг, сигнализирующий о дубле и посылаемый вниз по пути с рекурсивным изменением. Вдобавок давайте создадим флаг, сигнализирующий, не всплыли ли мы вверх с того уровня, где было дублирующееся значение, смежное с nil. Таким образом, у нас сохранится уловка, позволяющая добраться до nil, и вместе с тем мы сможем безопасно перезаписывать указатели. А если бы мы достигли уровня, имея этот флаг со значением true, мы переключаем узлы и устанавливаем его в false – так сообщается, что дубля в конце у нас уже нет.

Давайте пошагово распишем этот подход, попутно реализовав его.

Нам потребуется два аргумента: узел и изменившийся флаг, сигнализирующий, изменили ли мы узел, двигаясь вниз по рекурсивной цепочке.

func deDupe(node *LinkedList, changed bool) {}

Также нам понадобится булев флаг, указывающий, дошли мы до nil с дублем или нет.

func deDupe(node *LinkedList, changed bool) bool {}

Базовый случай – это когда следующий узел равен nil. Также давайте предусмотрим значение, позволяющее судить, не изменили ли мы узел на данном конкретном уровне рекурсии.

...
var didChange bool

if node.Next == nil {
...
} else {
...
}
...

Достигнув nil, мы должны знать, пришли ли мы с дублирующегося узла. Именно здесь нам пригодится параметр changed, который мы просто вернём вверх по цепочке.

...
if node.Next == nil {
    return changed
} else {
...
}
...

Если наш следующий узел – не nil, это означает, что мы можем напрямую изменять указатели. Так что давайте реализуем внутри нашей ветки else всю дополнительную логику, которая нам понадобится. Известно, что нам потребуется сравнивать дубли, так что добавим условие, позволяющее сопоставить значение актуального и последующего узла. Обратите внимание: есть очень важная разница между простым переприсваиванием node и переприсваиванием указателя (*node) на node. Переприсваивая node, мы не меняем исходный список напрямую. Вот почему по пути вниз нам требуется булев элемент changed – если мы придём от дубля, то и встреченное значение нужно перезаписать, так как это дубль. Но в данном случае мы не устанавливаем changed в true, поскольку имеем дело с последним из дублей. Если мы пришли не от дубля, то просто переприсвоим node к node.Next, так как именно node передаётся с функцией.

...
} else {
    if node.Val != node.Next.Val {
        if changed {
            *node = *node.Next
        } else {
            node = node.Next
        }
    } else {
        *node = *node.Next
        didChange = true
    }
}
...

Итак, с рекурсивной функцией мы почти управились. Теперь нужно её вызвать. Поскольку мы изменяем значения, идя вниз, нас по-настоящему волнует только всплытие булевых значений.

...
lastIsDupe := deDupe(node, didChange)
...

Так удаётся узнать, является ли дублем последнее значение в списке – что послужит нам уведомлением, должны ли мы перенаправить узел nil, найденный на этом уровне. Ведь возможно, что после вызова рекурсивной функции наш узел, переданный с ней, был изменён ещё до того, как мы правильно сбросили флаг lastIsDupe.

...
if lastIsDupe && node.Next != nil {
    node.Next = nil
    lastIsDupe = false
}

return lastIsDupe
...

Наконец, возвращаем флаг lastIsDupe. Если он в процессе всплытия по уровням рекурсии, то мы наткнёмся на предыдущий узел, а следующему узлу присвоим nil, тем самым удалив последний узел – который дублировался. После этого, сбросив флаг в false, мы сообщим на вышестоящие уровни, что дубля в конце уже нет.

Итак, давайте соберём всё вместе с кодом исходной функции, в котором предусмотрен вызов на верхнем уровне (обратите внимание, что сигнатура функции изменилось, поскольку на LeetCode соответствующие структуры (связные списки) называются ListNode):

func deleteDuplicates(head *ListNode) *ListNode {
    // by default these cases contain no dupes
    if head == nil || head.Next == nil {
        return head
    }

    lastIsDupe := deDupe(head, false)

    // the reasoning behind this condition
    // is the same as in the recursive fn
    if lastIsDupe && head.Next != nil {
        head.Next = nil
    } else if lastIsDupe {
        return nil
    }

    return head
}

func deDupe(node *ListNode, changed bool) bool {
    var didChange bool

    if node.Next == nil {
        return changed
    } else {
        if node.Val != node.Next.Val {
            if changed {
                *node = *node.Next
            } else {
                node = node.Next
            }
        } else {
            *node = *node.Next
            didChange = true
        }
    }

    lastIsDupe := deDupe(node, didChange)

    if lastIsDupe && node.Next != nil {
        node.Next = nil
        lastIsDupe = false
    }

    return lastIsDupe
}

Итак, мы добрались до конца, успешно решив задачу! Не забывайте, что это всего лишь один из вариантов решения – может быть, и не лучший. Его сильная сторона – последовательное изменение значений узлов в одном направлении (учитывая, что сложность по времени — O(n)), но такой подход влечёт серьёзные издержки, сопряжённые со сложностью на уровне операционной системы. Ведь все эти рекурсивные вызовы функций будут надстраиваться друг над другом в куче.

Источник