Question

You have what you hope is a linked list, but you are concerned that it may contain a cycle. Describe an algorithm FINDLOOP that takes a reference to the front of the list as input and either returns false if the list has no loops, true otherwise.

I would prefer the answer in pseudocode format. Thank you!

Answer 1

def FINDLOOP (head):
    if head=NULL   
       return false
slowPtr=head   
fastPtr=slowPtr.next   
while fastPtr!=NULL:   
   if fastPtr.next=NULL
       return false
fastPtr=fastPtr.next.next
slowPtr=slowPtr.next

if fastPtr=slowPtr
       return true
endwhile
return false   
enddef