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.
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 doesnt have loop.
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 #include /* 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; } OutputInserted 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.