# Floyd’s Cycle-Finding Algorithm

In this post, we are going to write a program to detect a loop in a linked list.
There are many ways to do it. Here is a great read: http://blog.ostermiller.org/find-loop-singly-linked-list

In our program, we will use the two-pointer method, also known as Floyd’s Cycle-Finding Algorithm. In this algorithm, we will use two pointers. We will one with twice the speed of other and if they ever meet there is a loop in the linked list.
Below is our program implementation:

// THis program calculates the number of occurrences of an element in the linked list
#include<stdlib.h>
#include<stdio.h>

// Creating a structure for linked list node
struct node
{
int data; // variable to store data in node
struct node *next; //pointer to store the address of the connected node
};

// This function will add a node at the end of the linked list
// This functions takes pointer to pointer of head and value to be appended into
// the linked list
void append(struct node **head_ref, int value)
{
// Creating a memory block using malloc to store the data and assigning
// it to a struct node pointer named temp
struct node *temp = (struct node *)malloc(sizeof(struct node)) ;

// assigning the data to the node
temp->data = value;

// assigning the next pointer to NULL, as
// it will be the last node of linked list
temp->next = NULL;

// if head is NULL, then we will just point the head node to
// the temp node created above and return
if(*head_ref == NULL)
{
*head_ref = temp;
return;
}

// creating a struct node pointer called trav to traverse the list
// to the end
struct node *trav = *head_ref;

// traversing the list to the end
while(trav->next != NULL)
trav = trav->next;

// pointing the next pointer of last node to the temp node
trav->next = temp;
}

// This function prints the linked list and takes the head pointer as
// its parameter
void print_list(struct node *head)
{
// traversing the linked list till the end and printing
// the data in the nodes
while(head != NULL)
{
printf("%d ", head->data);
head = head->next;
}

// printing new line after printing the whole linked list
printf("\n");
}

// This function returns 1 if there is a loop in the linked list
// and return 0 if there is no loop.
// one pointer runs at twice the speed of other pointer and if they both
// meet at some point then there is a loop
int detect_loop(struct node *head)
{
struct node *fast_ptr = head->next;

while(head != NULL && fast_ptr!= NULL && fast_ptr->next != NULL)
{
if(fast_ptr == head) return 1;
fast_ptr = fast_ptr->next->next;
head = head->next;
}

return 0;
}

// Main driver function
int main()
{
// this is to read input and write output in
// input.txt and output.txt files in the same folder
#ifndef LOCAL_TEST
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif

// creating head node of the linked list and assigning it to NULL
struct node *head = NULL;

// call the append function to add elements to the list
append(&head, 7);
append(&head, 8);
append(&head, 15);
append(&head, 12);
append(&head, 9);

printf("Printing List : ");

// printing the list with all elements
print_list(head);

// Detecting loop in the linked list
detect_loop(head) ? printf("Yes\n") : printf("No\n");

// creating a loop for testing
head->next->next->next = head;

// Detecting loop in the linked list
detect_loop(head) ? printf("Yes\n") : printf("No\n");

return 0;
}

Expected output:

Printing List : 7 8 15 12 9
Loop not found
Loop found

Time complexity : O(n)