# 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>>=typedefstructnode_s{void*data;structnode_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>>=intlist_has_cycle(NODE *list){NODE *fast=list;while(1){if(!(fast=fast->next))return0;if(fast==list)return1;if(!(fast=fast->next))return0;if(fast==list)return1; list=list->next;}return0;}

## Test

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

<<cycle-finder.c>>=#include<stdio.h>struct list_has_cycleintmain(){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");elseprintf("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");elseprintf("no cycle\n");return0;}

The output is as we expect:

Test without cycle: no cycle Test with cycle: cycle

Download code |