pythoncircular-list

Circular Linked list in python


def delete_node(head, value):
    p=head
    if p is None:
        return None
    while p.value!=value:
        p=p.next
        if p.next is head and p.value!=value:
            return head
    p.value=p.next.value
    if p.next==head:
        head=p
    p.next=p.next.next
    return head

The above is my code for deleting a node in a circular linked list based on value of the node! The code doesn't gimme result for this case-- I've only 1 element in the list and i deleted it.. So the resultant should be an empty set.. But because i took p.value=p.next.value it points back again to itself and the same value is in the list! Can anyone help me out! Thanx in advance! :)


Solution

  • The easiest solution here is to have a dummy node that points to itself in case of an empty list. As a consequence in an empty list we have one node that points to itself (the dummy), in a list with one element the dummy points to the element and the element points to the dummy.

    Avoids the need for any special cases and generally simplifies the code. To check if the list is empty you can then just do dummy.next is dummy, also nice.