Cycle detection

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.