Detecting a loop or cycle  in linked list is a very common questions asked in the interview.Generally , several methods/approaches  are questioned about solving this question. This question involves a major algorithm which is very useful in detecting cycles like in graphs and linked list. .

A cycle in graph makes it Acyclic where as in linked list it’s points to the same address in memory.

Prequesite:- Singly Linked List

The cycle in linked list can be detect by using Hashing and Floyd’s cycle-finding Algorithm.

Basic Approach :-

We need to make changes to the structure of the Linked list.

• Have a visited Flag with each linked list
• Traverse the coupled list and keep marking visited nodes.
• If you see a visited node more than once , then there is a loop.

Now, the loop is detected but the problem is that it needs a extra data with every node which increases space complexity to O(n), where ‘n’ is number of nodes.

Structure of the node looks like :-

Struct node

{

  int data;

  int flag;

  Struct node *next;

}

Hashing :-

• Linearly traversing the link list node by node till the end of the list .
• Storing the address of each in hash table with the information on link list as key value and address as index value.
• If hash has duplicate entry , then we can say that the linked list has loop in it .

The time complexity of the approach is O(N) , where ‘N’ is the size of the linked list.

Also, it makes a copy of the link list in Hash table , so it consumes a O(N) space.

Using Floyd’s cycle-finding Algorithm:

This Algorithm maintains two pointers ,let say ptr1 and ptr2 .

The first pointer ptr1 is incremented by 1 unit and the other pointer is incremented by 2 unit.

The “Tortoise and Hare Algorithm” is another name  for the Algorithm. At each step , the tortoise is moved by one step and hare is moved by two steps. The point at which both the tortoise and hare have same values is declared to form a cycle.

Basically  this algorithm is used to detect cycles in the directed Graph.

Let us consider the situation of cycle in linked list.

• We initially mark the two pointer , ptr1 and ptr2 pointing to the head of link list.

• Traversing the link list with the three conditions in the while loop

1. Ptr1 upto null

2. Ptr2 upto null

3. Ptr2->next utpo null

• Each time it comes outside the while loop , ptr1 is incremented by 1 unit and ptr2 is incremented by 2 unit.

• And if, ptr1==ptr2 , the cycle is detected.
  
  

#include <stdio.h>
#include <stdlib.h>


struct Node
{
    int info;                  //variable to store data 
    struct Node* next;         // next pointer 
};

//function to detect cycle 
int cycle_detect(struct Node* head)
{
    struct Node* ptr1 = head, *ptr2=head;     //two pointers ptr1 and ptr2      
    while (ptr1 && ptr2 && ptr2->next)        // run loop till these 3 conditions
    {
        ptr1=ptr1->next;                      //increment ptr1 by 1 unit
        ptr2=ptr2->next->next;
        //ptr2 by 2 unit
        //when ptr1 and ptr2 point to same node 
        if(ptr1==ptr2){                               
            printf("A cycle is detected at %d", ptr1->info);
        return 1;
        }
    }

   return 0;
}


void addtobeg(struct Node** head, int data)
{
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->info = data;
    newNode->next = *head;
    *head = newNode;
}



int main()
{

    int ar[] = { 5, 10, 4, 2, 1};
    int n = sizeof(ar)/sizeof(ar[0]);

    struct Node* head = NULL;
    for (int i = n - 1; i >=0; i--)
        addtobeg(&head, ar[i]);

    head->next->next->next=head;
    cycle_detect(head);


    return 0;
}