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

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

Пример для целочисленного списка; head и tail могут измениться:

type Node struct {
    Value int
    Prev, Next *Node
}

func RemoveRepeated(head *Node) (*Node, *Node) {
    counts := make(map[int]int)
    for p := head; p != nil; p = p.Next { counts[p.Value]++ }
    var tail *Node
    for p := head; p != nil; {
        next := p.Next
        if counts[p.Value] > 1 {
            if p.Prev != nil { p.Prev.Next = next } else { head = next }
            if next != nil { next.Prev = p.Prev }
            p.Prev, p.Next = nil, nil
        } else { tail = p }
        p = next
    }
    return head, tail
}

Время O(n), дополнительная память O(u) для уникальных значений. Предполагается корректный ациклический двусвязный список без конкурентного изменения.