-
Floyd cycle detection
over 9 years ago
-
over 9 years ago
Floyd cycle detection algo used to detect the infinite loops inside lists, symlinks, state machines.
Make two pointer from starting of the list , increment one pointer by 1 and another by 2 on every iteration if both pointer meets it means there is loop.
If second pointer reaches at the end , it means there is no loop.
so complexity are O(n) time and O(1) space
-
over 9 years ago
Hi Avish,
Please go over following link: http://codingfreak.blogspot.com/2012/09/detecting-loop-in-singly-linked-list_22.html I think this will help you in what you are looking.
-
over 9 years ago
hi Avish , please go over the following link====>
- List item
1=> http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
2=> http://www.siafoo.net/algorithm/10
-
over 9 years ago
http://codingfreak.blogspot.com/2012/09/detecting-loop-in-singly-linked-list_22.html
I hope this link is helpful. This explains the complete "Floyd's Cycle Detection Algorithm", also known as "Tortoise and Hare Algorithm".
It also has the complete pseudo code.
4 Answer(s)