Cycle detection is an easy algorithm according to Hacker Hank, but what if I ask you to create an algorithm to find a Ring Circuit in an Electrical Network? That would be completely different.
That's it, now that we understood that this silly algorithm could help us to solve real-world problems let's learn how to implement it.
A linked list or a graph has a cycle when a existent node gets referenced by another one and, in theory it can be identified by walking through the graph and, once you pass through a node which you had already passed before.
An algorithm could save each node it came across and test if the current one exists in this list of nodes, but take care it could be a highly memory consuming solution, we will keep away from this solution.
If you have the access to the Node implementation you can set a flag to mark those nodes which you've already visited, but the challenge related doesn't allow us to do it.
Then the right solution is to iterate over the data structure using two pointers, the first one move one step each time and the second one move two steps each time when those two pointers meet we found the cycle.
This is the solution using Python 3:
def has_cycle(head): hare = head turtle = head while turtle != None and hare != None: turtle = turtle.next hare = hare.next.next if hare.next != None else None if hare != None and hare == turtle: return True return False
I hope you've enjoyed, see you soon.