Cycle detection in linked list with the Hare and Tortoise approach

user_772726 0
Viewed 8586

I understand that in order to detect a cycle in a linked list I can use the Hare and Tortoise approach, which holds 2 pointers (slow and fast ones). However, after reading in wiki and other resources, I do not understand why is it guaranteed that the two pointers will meet in O(n) time complexity.

floyd-cycle-finding detection cycle linked-list algorithm
4 Answers

this is the while loop of tortoise and hare algorithm:

    while tortoise:
        hare = hare.next
        tortoise = tortoise.next
        # if not hare, states that i have a single node.
        # hare.next means that we have a tail value. So we do not have a cycle
        if (not hare) or (not hare.next):
            return False
        else:
            hare = hare.next
        if tortoise == hare:
            return True

Although hare moves 2 steps forward, meaning that there is a chance that it might loop over and over again within the cycle, and touch multiple nodes over and over again, technically speaking, it is all happening within one while loop.

user_102628050
Related