C Programming Code Examples C > Linked Lists Code Examples Program to Detect the Cycle in a Linked List Program to Detect the Cycle in a Linked List This C Program detects if there is a cycle that exists in a linked list. #include <stdio.h> #include <stdlib.h> struct node { int j; struct node *next; }; void create(struct node **); void makecycle(struct node **); void release(struct node **); int detectcycle(struct node *); int main() { struct node *p = NULL; int result; printf("Enter data into the list\n"); create(&p); makecycle(&p); //comment it to avoid cycle creation printf("Identifying if a cycle exists.\n"); result = detectcycle(p); if (result) { printf("Cycle detected in the linked list.\n"); } else { printf("No cycle detected in the linked list.\n"); } release (&p); return 0; } void makecycle(struct node **p) { struct node *rear, *front; int n, count = 0, x; front = rear = *p; while (rear->next != NULL) { rear = rear->next; count++; } if (count) { n = rand() % count; } else { n = 1; } for (x = 0; x < n - 1; x++) { front = front->next; } rear->next = front; /*At this point a cycle is generated in the list*/ } int detectcycle(struct node *head) { int flag = 1, count = 1, x; struct node *p, *q; p = q = head; q = q->next; while (1) { q = q->next; if (flag) { p = p->next; } if (q == p) { /*Deleting the loop to deallocate the list*/ q = q->next; while (q != p) { count++; q = q->next; } q = p = head; for (x = 0; x < count; x++) { q = q->next; } while (p != q) { p = p->next; q = q->next; } q->next = NULL; return 1; } else if (q->next == NULL) { return 0; } flag = !flag; } } void create(struct node **head) { int c, ch; struct node *temp, *rear; do { printf("Enter number: "); scanf("%d", &c); temp = (struct node *)malloc(sizeof(struct node)); temp->j = c; temp->next = NULL; if (*head == NULL) { *head = temp; } else { rear->next = temp; } rear = temp; printf("Do you wish to continue [1/0]: "); scanf("%d", &ch); } while (ch != 0); printf("\n"); } void release(struct node **head) { struct node *temp = *head; temp = temp->next; while ((*head) != NULL) { free(temp); temp = *head; (*head) = (*head)->next; } }
