Given a circular linked list, implement an algorithm which returns node at the begin- ning of the loop. DEFINITION Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list. EXAMPLE input: A -> B -> C -> D -> E -> C [the same C as earlier] output: C

__author__ = 'nitin'

class Node:
    def __init__(self,initdata):
        self.data=initdata
        self.next=None
    def getData(self):
        return self.data
    def setData(self,item):
        self.data=item
    def getNext(self):
        return self.next
    def setNext(self,item):
        self.next=item

def find_circular_node(n0):
    n1=n0
    n2=n0
    while n2.getNext() is not None:
        n1=n1.getNext()
        n2=n2.getNext().getNext()
        if n1==n2:
            break
    if n2.getNext() is None:
        return None
    n1=n0
    while n1!=n2:
        n1=n1.getNext()
        n2=n2.getNext()
    return n2.getData()

n0=Node('A')
n1=Node('B')
n2=Node('C')
n3=Node('D')
n4=Node('E')
n0.setNext(n1)
n1.setNext(n2)
n2.setNext(n3)
n3.setNext(n4)
n4.setNext(n2)

print find_circular_node(n0)