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)

Show CommentsClose Comments

Leave a comment