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.

Detect cycle in a linked list

Fig:1.1

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.

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.