C Program to Find Cycle in a Linked List

  • Write a C program to detect a loop in a linked list.
  • How to check whether a linked list contains a cycle.

Given a Singly list, we have to find whether given linked list contains a cycle. A loop in a linked list means there is no tail node in a linked list, every node of link list is pointing to some other node of linked list.

Method 1 : Fast and Slow pointer method.
Algorithm to detect cycle in a linked list
Let "head" be the head pointer of given linked list.
  1. Let, "slow" and "fast" be two node pointers pointing to the head node of linked list.
  2. In every iteration, the "slow" pointer moves ahead by one node(slow = slow->next;) whereas "fast" pointer moves two nodes at a time(fast = fast->next->next;).
  3. If linked list contains a loop, "slow" and "fast" pointers will eventually meet at the same node, thus indicating that the linked list contains a loop.
  4. If pointers do not meet then linked list doesn’t have loop.
This algorithm is known as Floyd’s Cycle-Finding Algorithm

In this program, we will use a user defined function "findloop" which takes a pointer to the head node of linked list as input from user and check whether linked list contains a cycle or not by implementing above algorithm. 

void findloop(struct node *head) {
    struct node *slow, *fast;
    slow = fast = head;
  
    while(slow && fast && fast->next) {
        /* Slow pointer will move one node per iteration whereas 
        fast node will move two nodes per iteration */
        slow = slow->next;
        fast  = fast->next->next;
        if (slow == fast) {
           printf("Linked List contains a loop\n");
           return;
        }
    }
    printf("No Loop in Linked List\n");
}

C program to check cycle in linked list

#include <stdio.h>
#include <stdlib.h>
 
/* A structure of linked list node */
struct node {
  int data;
  struct node *next;
} *head;

void initialize(){
    head = NULL;
}

/* 
Given a Inserts a node in front of a singly linked list. 
*/
void insert(int num) {
    /* Create a new Linked List node */
    struct node* newNode = (struct node*) malloc(sizeof(struct node));
    newNode->data  = num;
    /* Next pointer of new node will point to head node of linked list  */
    newNode->next = head;
    /* make new node as new head of linked list */
    head = newNode;
    printf("Inserted Element : %d\n", num);
}

void findloop(struct node *head) {
    struct node *slow, *fast;
    slow = fast = head;
  
    while(slow && fast && fast->next) {
        /* Slow pointer will move one node per iteration whereas 
        fast node will move two nodes per iteration */
        slow = slow->next;
        fast  = fast->next->next;
        if (slow == fast) {
           printf("Linked List contains a loop\n");
           return;
        }
    }
    printf("No Loop in Linked List\n");
}
/*
 Prints a linked list from head node till tail node 
*/
void printLinkedList(struct node *nodePtr) {
  while (nodePtr != NULL) {
     printf("%d", nodePtr->data);
     nodePtr = nodePtr->next;
     if(nodePtr != NULL)
         printf("-->");
  }
}
 
int main() {
    initialize();
    /* Creating a linked List*/
    insert(8);  
    insert(3); 
    insert(2); 
    insert(7);
    insert(9);
    
    /* Create loop in linked list. Set next pointer of last node to second node from head */
    head->next->next->next->next->next = head->next;

    findloop(head);
    return 0;
}
Output
Inserted Element : 8
Inserted Element : 3
Inserted Element : 2
Inserted Element : 7
Inserted Element : 9
Linked List contains a loop
Method 2 : Using a Hash Table.
Algorithm to detect cycle in a linked list
  1. Traverse the given linked list and put the address of each node in a Hash table.
  2. If you reach a node whose next pointer is NULL, then given linked list doesn't contain s cycle.
  3. If address of any node already exist in Hash table, it means we are visiting this node again and linked list contains a cycle.
Posted by
Labels: