Remove Duplicates Python Circular Linked List

[Reethu_1]

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)
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

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.

[slate]

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)
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


visited=set()
values=set()
current_node=last
values.add(current_node.value)
while current_node not in visited:
    visited.add(current_node)
    while current_node.next.value in values and current_node.next not in visited:
        current_node.next=current_node.next.next
    values.add(current_node.next.value)
    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)))

[TrustyTony]

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.

[slate]

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:
    visited.add(current_node)
    values=set()
    values.add(current_node.value)
    while current_node.next.value in values and current_node.next not in visited:
        current_node.next=current_node.next.next
    values.add(current_node.next.value)
    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?

[Gribouillis]

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)
    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
    return head

def circ_reversed(head):
    """return a reversed circular list"""
    if head is None:
        return None
    rev_head = rev_last = Node(head.value)
    current = head.next
    while current is not head:
        rev_head = Node(current.value, rev_head)
        current = current.next
    rev_last.next = rev_head
    return rev_head

def circ_reversed_duplicates_removed(head):
    """return a reversed circular list with duplicates removed"""
    if head is None:
        return None
    rev_head = rev_last = Node(head.value)
    current = head.next
    while current is not head:
        if current.value != rev_head.value:
            rev_head = Node(current.value, rev_head)
        current = current.next
    while rev_head.next is not None and rev_head.value == rev_last.value:
        rev_head = rev_head.next
    rev_last.next = rev_head
    return rev_head

def circ_duplicates_removed(head):
    """return a circular list with duplicates removed"""
    temp = circ_reversed_duplicates_removed(head)
    return circ_reversed(temp)

def circ_to_python_list(head):
    """convert a circular list to a python list"""
    if head is None:
        return []
    result = [ head.value ]
    current = head.next
    while current is not head:
        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]
"""

[TrustyTony]

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

def Node(value, head=None):
    if head is not None and head.value == value:
        return head
    else:
        return NodeClass(value, head)

def example_list():
    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
    return head

def circ_to_python_list(head):
    """convert a circular list to a python list"""
    if head is None:
        return []
    result = [head.value]
    current = head.next
    while current is not head:
        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]
"""

[slate]

/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.

[TrustyTony]

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)
    head = Node(2, last)
    head = Node(5, head)
    head = Node(8, head)
    head = Node(8, head)
    head = Node(8, head)
    head = Node(2, head)
    val = 3
    if last.value != val:
        head = Node(val, head)
    last.next = head
    return head

Output:

[2, 8, 5, 2, 3]

That can not do on the fly as in the middle that is allowed as there is more values added still. That normally would still take full pass of the list as the list is single linked (even it is circular). It would require quite gimmick to do on the fly update with inserts and deletions of nodes. If you insert different value between equal values, both values should appear.