Tortoise and Hare

What is cycle ?

We read about water cycle . From Cloud rain falls . In heat water go to sky and it becomes cloud again . And cloud becomes rain in rainy day . It happens infinity times .This is a cycle .

How can it be held in Linked List?

Let’s see it with singly linked list .

As we have to less handle the connection . Here there is no previous linked list .

Same process will held in doubly linked list .

Let’s take a linked list -

10 30 40 50 60

If we mistakenly don’t write NULL after 60 and write B after 60 what’ll happen?

It will become a cycle. It will run for whole life . Meaning infinity times . It is a cycle of linked list .

We have to detect it . Because we cannot work with it . We will get TLE or Compiler will be hanged .

How to detect?

There is an algorithm to detect it .

It is called SlowFast Algorithm or Tortoise and Hare Algorithm or Two Pointer Technique

We have to take two pointer .

Tortoise pointer will go to the next pointer and Hare pointer will jump to 3rd pointer . Meaning Hare will pass 2 index and tortoise 1 index . And they both will be in the tail . It means they have a cycle .

If it is cycle the two pointer will be in same index at any point .

Implementation

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Node *head = new Node(10);
    Node *a = new Node(20);
    Node *b = new Node(30);
    Node *c = new Node(40);

    Node *d = new Node(50);

    Node *e = new Node(60);
    head->next = a;
    a->next = b;
    b->next = c;
    c->next = d;
    d->next = e;
    e->next = a;

    // Detect
    Node *slow = head;
    Node *fast = head;
    int f = 0;
    while (fast != NULL && fast->next != NULL)

    {

        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast)
        {
            f = 1;
            // Cycle detected
            break; // As There is no end . It will held for whole life
        }
    }
    if (f)

        cout << "Cycle DETECTED\n";

    else
        cout << "No Cycle\n";
}