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.
/*
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.



Related Contents to follow