Удалить дубликаты Циклический связанный список Python

Question

Необходимо удалить дублирующее событие с тем же значением. Если (связанный) список проходится с головы содержит последовательность 3,2,8,8,8,5,2,3 после вызова

last = Node(3) 
head = Node(2, last) 
head = Node(5, head) 
head = Node(8, head) 
head = Node(8, head) 
head = Node(8, head) 
head = Node(2, head) 
head = Node(3, head) 
last.next = head 

Теперь список, проходится с головы, должен содержать 3, 2, 8, 5, 2 или 2, 8, 5, 2, 3. Значение «head» equal None представляет собой пустой список (список с нулевыми элементами). Как я могу это достичь. Это может быть одним из самых простых способов достижения. Поскольку я новичок в Python, мне нелегко это делать.

Answer 1

Перейдите по круговому списку, отбросив значения, которые уже появились (но сначала проверяйте, был ли этот узел уже просмотрен).

В принципе, начинайте с головы и каждый раз проверяя, находится ли значение узла в наборе. Если он не добавляет значение к набору и не переходит дальше. В противном случае удалите узел (соедините предыдущий и следующий узлы вместе). Когда вы вернетесь на первый узел (вы никогда не удалите первый узел), остановите.

Answer 2

Вам необходимо отслеживать значения для каждого узла и исходного объекта Node, так как это круговой связанный список. Ваш код для класса Node может отличаться, но его легко изменить.

class Node(object): 
    def __init__(self, data, next_=None): 
     self.data = data 
     self.next = next_ 

def ll_remove_dups(curr): 
    start_node = curr 
    values_seen = {curr.data} 
    while curr.next is not start_node: 
     if curr.next.data in values_seen: 
      curr.next = curr.next.next 
     else: 
      values_seen.add(curr.next.data) 
      curr = curr.next 

def ll_traverse(curr): 
    start_node = curr 
    yield curr.data 
    while curr.next is not start_node: 
     yield curr.next.data 
     curr = curr.next 

if __name__ == "__main__": 
    last = Node(3) 
    head = Node(3, Node(2, Node(8, Node(8, Node(8, Node(5, Node(2, last))))))) 
    last.next = head 

    print list(ll_traverse(head)) # [3, 2, 8, 8, 8, 5, 2, 3] 
    ll_remove_dups(head) 
    print list(ll_traverse(head)) # [3, 2, 8, 5]