Some days ago I was in an interview for a position at a company when they asked me to do a function which detects if a list is either cyclic or acyclic. I need to be honest, I didn’t know how to solve the problem and I had a limited time to solve the question then I couldn’t wonder on how to solve that for ages then I googled it. I found the Floyd’s cycle-finding algorithm, also known as “the tortoise and the hare algorithm” or “the turtle and the rabbit algorithm”. I found some examples in languages such as Java and Python but nothing using PHP, then I did it by my own based on what I saw. The result code is below:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
function isCyclic(Node $node) { if ($node == null) { return false; } $turtle = $node; $rabbit = $node->next; while ($rabbit != null) { if ($rabbit === $turtle) { return true; } else if ($rabbit->next == null) { return false; } else { $turtle = $turtle->next; $rabbit = $rabbit->next->next; } } return false; } |
I hope this snippet can help anybody out there.
by 
Hi, How can call this method? (Node $next) is a class?
Hi Juan,
Yes Node is a class, very simple but it’s a class.
class Node{
public $next;
}
This would do the trick.