Skip to content

Instantly share code, notes, and snippets.

@ptigas
Created March 3, 2012 21:18
Show Gist options
  • Save ptigas/1968328 to your computer and use it in GitHub Desktop.
Save ptigas/1968328 to your computer and use it in GitHub Desktop.
Example of Floyd algorithm for loop detection
'''
Example of Floyd algorithm for loop detection
'''
class Node :
def __init__(self, data) :
self.next = None
self.data = data
def __str__(self) :
return str(self.data)
class LinkedList :
def __init__(self) :
self.head = None
def add_node(self, data):
if self.head == None :
self.head = Node(data)
else :
tmp = Node(data)
tmp.next = self.head
self.head = tmp
def add_loop(self, f, t) :
node = self.head
i = 0
node_f = None
node_t = None
while node != None :
i += 1
if i == f :
node_f = node
if i == t :
node_t = node
node = node.next
node_f.next = node_t
def print_list(self):
node = self.head
while node != None :
print node.data
node = node.next
def toirtoise_and_hare(l) :
tortoise = l.head
hare = l.head
steps = 0
while True:
if hare == None :
return (steps, 'No loop found')
hare = hare.next
if hare == None :
return (steps, 'No loop found')
hare = hare.next
tortoise = tortoise.next
if hare == tortoise:
#print hare, tortoise
return (steps, 'Loop found')
steps += 1
l = LinkedList()
for i in xrange(1000) :
l.add_node(i)
l.add_loop(800, 200)
print toirtoise_and_hare(l)
#l.print_list()
Copy link

ghost commented Oct 15, 2014

I don't understand how this is working, because the list type has no method "head", and no method "next".

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment