Duplicate occurance of the same value has to be removed. If the (linked)list traversed from head contains sequence 3,2,8,8,8,5,2,3 after calling

``````last = Node(3)
``````

Now, the list, traversed from head, should contain 3, 2, 8, 5, 2 or 2, 8, 5, 2, 3. The value of ‘head’ equal None represents an empty list (a list having zero elements). How would I achieve this. This may be one of the easiest way to achieve. Since I am new to Python am having hard time in doing this.

4
Contributors
7
Replies
71
Views
3 Years
Discussion Span
Last Post by pyTony

If you remove the duplicates form the linked list: 3,2,8,8,8,5,2,3 then it remains: 3,2,8,5. I do not understand why you expect a list with duplicates.

If the Node object is something like this:

``````class Node(object):
def __init__(self, value, next=None):
self.next=next
self.value=value
``````

Then removing the duplicates is something like this (the whole code):

``````class Node(object):
def __init__(self, value, next=None):
self.next=next
self.value=value

last = Node(3)

visited=set()
values=set()
current_node=last
while current_node not in visited:
while current_node.next.value in values and current_node.next not in visited:
current_node.next=current_node.next.next
current_node=current_node.next

nodes=list()
current_node=last
nodes.append(last)
while current_node.next is not last:
nodes.append(current_node.next)
current_node=current_node.next

print (",".join((str(node.value) for node in nodes)))
``````

Define the Node to keep reference of last created object and make it return that if node value is same as last before in the `__new__` class method or define Node as a factory function doing the same.

I have read the requirement once more. Only the sequential duplicates are to be removed.
This can be done with this:

``````visited=set()
current_node=last
while current_node not in visited:
values=set()
while current_node.next.value in values and current_node.next not in visited:
current_node.next=current_node.next.next
current_node=current_node.next
``````

I do not undterstand PyTony's advice completly. Especially, how do you handle the `last.next = head` statement. Can you show me some code?

Edited by slate: clarification

Assuming that all the lists are circular (see the title), it can be done without a set. The idea is that the lists are very easy to reverse because they are built in the reversed order.

In the code below, I write a function to reverse a circular list, then by modifying this function, I write a function to reverse the list while removing duplicates. Combining the two gives the algorithm to remove (consecutive) duplicates.

``````class Node(object):
def __init__(self, value, next=None):
self.next=next
self.value=value

def example_list():
last = Node(3)

"""return a reversed circular list"""
return None
current = current.next

"""return a reversed circular list with duplicates removed"""
return None
current = current.next

"""return a circular list with duplicates removed"""
return circ_reversed(temp)

"""convert a circular list to a python list"""
return []
result.append(current.value)
current = current.next
return result

if __name__ == "__main__":
example = example_list()
print(circ_to_python_list(example))
rev = circ_duplicates_removed(example)
print(circ_to_python_list(rev))

""" my output -->
[3, 2, 8, 8, 8, 5, 2, 3]
[3, 2, 8, 5, 2]
"""
``````

Edited by Gribouillis

Here is factory function code, which does not deal with circular duplicate with head value, removal of which should be done separately. Otherwise this Node factory does not produce consecutive equal value nodes but returns the previous node.

``````class NodeClass(object):
def __init__(self, value, next=None):
self.value = value
self.next = next

else:

def example_list():
last = Node(3)

"""convert a circular list to a python list"""
return []
result.append(current.value)
current = current.next
return result

if __name__ == "__main__":
example = example_list()
print(circ_to_python_list(example))

"""Output:
[3, 2, 8, 5, 2, 3]
"""
``````

Edited by pyTony

interesting!

/PyTony
1. The output is incorrect. There are two "3"-s after eachother. The first and the last.
2. If None is allowed as the next node, or the next node can be changed afterwards, then you cannot say at creation time if the next node has, or ever will have, the same value or not.

That's why I did not understand, and that has not changed.

None is not value of node, it is the head pointer (that can only be None for empty list). Yes, the head should not be inserted in the end if it is same as last one's value (example_list function).

``````def example_list():
last = Node(3)
val = 3
if last.value != val:
``````[2, 8, 5, 2, 3]