0 points

Floyd's Cycle Detection Algorithm - aka "The Tortoise and the Hare"


dashboard

Tue Dec 31 2019 19:00:00 GMT+0000 (UTC)

Posted by @solitaire_4_07 #algorithms #logic #interesting

tortoise = top
hare = top

forever:
     if hare == end :
         return 'No Loop Found'
     hare = hare.next
 
     if hare == end :
         return 'No Loop Found'
     hare = hare.next
 
     tortoise = tortoise.next
 
     if hare == tortoise:
         return 'Loop Found'
content_copy

"top" refers to the top of the list. "end" refers to the end of the list. Lines 1-2: The tortoise and the hare are two pointers that are initialized with the value of the "top" of the list. Lines 5-6: IF the hare equals the end of the list, the algorithm detects and returns that "no loop is found" and the code stops running. If not, this step is skipped and moves on to line 7. Line 7: The value of hare is incremented to the next value in the list. Lines 9-11: The previous cycle is repeated. If no loop is found again, then the hare's value increments to the next item in list. Line 13: The tortoise increases to the next item in the list. By this point, note that the hare has increased by two spots, while the tortoise has gone up by just one. Lines 15-16: If the hare equals the tortoise, a Loop has been detected. If not, the code between lines 5-16 repeats with the value of tortoise and hare at line 14. The cycle continues until a loop is either found or not found.



>> Browse more code snippets

more_vert