Floyd's cycle-finding algorithm (C)

From LiteratePrograms

Other implementations: C | Scheme

Floyd's cycle-finding algorithm, also known as the Tortoise and the Hare, detects a cycle in a list by using two pointers, a slow pointer ("tortoise") that walks the list one element at the time, and a fast pointer ("hare") that walks it two at a time. If there is a cycle, at some point the hare will overtake the tortoise; if there is no cycle, the hare gets to the end of the list first.

Node

To represent a node, we use a simple struct, containing a data pointer and a pointer to the next node. The data pointer is not used in this article, but is included for completeness. We use the first node to represent the whole list.

<<struct>>=
typedef struct node_s {
	void *data;
	struct node_s *next;
} NODE;

The algorithm

The list argument is used as the "tortoise", and is incremented by one node for each iteration. fast is the "hare", and starts out equal to list. Each iteration will increment fast and compare it to list twice. If they are equal, we have found a loop, and return 1 to indicate that.

<<list_has_cycle>>=
int list_has_cycle(NODE *list)
{
	NODE *fast=list;
	while(1) {
		if(!(fast=fast->next)) return 0;
		if(fast==list) return 1;
		if(!(fast=fast->next)) return 0;
		if(fast==list) return 1;
		list=list->next;
	}
	return 0;
}

Test

To test the algorithm, we create 5 nodes, linked together.

<<cycle-finder.c>>=
#include<stdio.h>
struct
list_has_cycle
int main()
{
	NODE n1, n2, n3, n4, n5;
	n1.next=&n2;
	n2.next=&n3;
	n3.next=&n4;
	n4.next=&n5;
	n5.next=NULL;
	printf("Test without cycle: ");
	if(list_has_cycle(&n1)) printf("cycle\n");
	else printf("no cycle\n");

Seeing that we didn't get any false positives, we create a loop by letting the last node point to third node.

<<cycle-finder.c>>=
	n5.next=&n3;
	printf("Test with cycle: ");
	if(list_has_cycle(&n1)) printf("cycle\n");
	else printf("no cycle\n");
	return 0;
}

The output is as we expect:

Test without cycle: no cycle
Test with cycle: cycle

Download code