Hui Guys please let me know How to break cycle in circular single link list?

hey,

There's an algorithm called Floyd-cycle finding algorithm.

Briefly, start from a node and traverse the list in steps of one and two using two
pointers. Eventually, both the pointers will coincide if there exists a cycle in the linked list.

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.

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.

Below is the algorithm

#include<stdio.h>


typedef struct node_s {
void *data;
struct node_s *next;
} NODE;


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;
}


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");


n5.next=&n3;

printf("Test with cycle: ");
if(list_has_cycle(&n1)) printf("cycle\n");
else printf("no cycle\n");

return 0;
}

__________________
Venkat
knowledge is Power