cc 2.6

findloop.py

# 2.6 Given a circular linked list, implement an algorithm which returns the node at the beginning of the loop.
#slower and faster pointers

from LinkedList import Node, LinkedList

def findloop(ls):
    p1 = ls.head
    p2 = ls.head
    if p2 is None or p2.next is None:
        return null
    while p2.next is not None:
        p1 = p1.next
        p2 = p2.next.next
        if p1 == p2:
            break

    p1 = ls.head
    while p1 != p2:
        p1 = p1.next
        p2 = p2.next
    print 'the loop starts at', p2.data
    return p2

#test

ls = LinkedList()
for i in range(10):
    ls.AddNode(i)
start = Node(80)
start.next = ls.head.next
ls.head.next = start
ls.end.next = start        
findloop(ls)