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 a completely different scenario.
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 you are walking through it and you reach the same node that you've already reached.
You could save each node and test if the current one is in this list of nodes, but it could be a highly memory consuming solution and we will keep away from it.
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.