• • Write a C Program to Detect cycle in a linked list. This is a very basic linked list interview question. Let us see an example, below linked list (figure 1.1 ) has a cycle because  node 2 or node 3  would be visited more than once if we traverse the list. A linked list must have a cycle if any node is visited more than once while traversing the list.

## C Program to Detect cycle in a linked list

#### Floyd’s Cycle-Finding Algorithm” also known as “The Tortoise and the Hare Algorithm”

This is the most efficient algorithm to find cycle in a linked list with O(n) time complexity. In this method following steps are taken

1. Traverse the linked list using two pointers ( slow pointer and fast pointer).
2. Move slow pointer by one and fast pointer by two.
3. If the linked list has a cycle ,the slow pointer and fast pointer will meet at a certain node.
4. If the linked list has a no cycle ,the slow pointer and fast pointer will never meet.
```/*
Detect a cycle in a linked list. Note that the head pointer may be 'NULL' if the list is empty.

A Node is defined as:
struct Node {
int data;
struct Node* next;
}
*/

return false;
return false;
while( slow_ptr && fast_ptr && fast_ptr->next)
{
slow_ptr = slow_ptr->next;
fast_ptr = fast_ptr->next->next;
if( slow_ptr == fast_ptr)
return true;
}
return false;
}
```