# Write C Program to Detect cycle in a linked list

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
*

*Traverse the linked list using two pointers ( slow pointer and fast pointer).**Move slow pointer by one and fast pointer by two.**If the linked list has a cycle ,the slow pointer and fast pointer will meet at a certain node.**If the linked list has a no cycle ,the slow pointer and fast pointer will never meet.*

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
/* 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; } */ bool has_cycle(Node* head) { if(head == NULL) return false; if(head->next == NULL) return false; Node* slow_ptr = head; Node* fast_ptr = head; 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; } |

*At link https://www.hackerrank.com/challenges/detect-whether-a-linked-list-contains-a-cycle you can write your own method to test the solution.*

## Leave a Reply