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

- Let, "slow" and "fast" be two node pointers pointing to the head node of linked list.
- 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;).
- 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.
- If pointers do not meet then linked list doesn’t have loop.

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

- Traverse the given linked list and put the address of each node in a Hash table.
- If you reach a node whose next pointer is NULL, then given linked list doesn't contain s cycle.
- If address of any node already exist in Hash table, it means we are visiting this node again and linked list contains a cycle.