C Program to Detect Cycle in a Linked List

This C Program detects if there is a cycle that exists in a linked list.

Here is a source code of the C Program to detect the cycle in a linked list. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C Program to Detect the Cycle in a Linked List 
  3.  */
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6.  
  7. struct node
  8. {
  9.     int num;
  10.     struct node *next;
  11. };
  12.  
  13. void create(struct node **);
  14. void makecycle(struct node **);
  15. void release(struct node **);
  16. int detectcycle(struct node *);
  17.  
  18. int main()
  19. {
  20.     struct node *p = NULL;
  21.     int result;
  22.  
  23.     printf("Enter data into the list\n");
  24.     create(&p);
  25.     makecycle(&p); //comment it to avoid cycle creation
  26.     printf("Identifying if a cycle exists.\n");
  27.     result = detectcycle(p);
  28.     if (result)
  29.     {
  30.         printf("Cycle detected in the linked list.\n");
  31.     }
  32.     else
  33.     {
  34.         printf("No cycle detected in the linked list.\n");
  35.     }
  36.     release (&p);
  37.  
  38.     return 0;
  39. }
  40.  
  41. void makecycle(struct node **p)
  42. {
  43.     struct node *rear, *front;
  44.     int n, count = 0, i;
  45.  
  46.     front = rear = *p;
  47.     while (rear->next != NULL)
  48.     {
  49.         rear = rear->next;
  50.         count++;
  51.     }
  52.     if (count)
  53.     {
  54.         n = rand() % count;
  55.     }
  56.     else
  57.     {
  58.         n = 1;
  59.     }
  60.     for (i = 0; i < n - 1; i++)
  61.     {
  62.         front = front->next;
  63.     }
  64.     rear->next = front;
  65.     /*At this point a cycle is generated in the list*/
  66. }
  67.  
  68. int detectcycle(struct node *head)
  69. {
  70.     int flag = 1, count = 1, i;
  71.     struct node *p, *q;
  72.  
  73.     p = q = head;
  74.     q = q->next;
  75.     while (1)
  76.     {
  77.         q = q->next;
  78.         if (flag)
  79.         {
  80.             p = p->next;
  81.         }
  82.         if (q == p)
  83.         {
  84.             /*Deleting the loop to deallocate the list*/
  85.             q = q->next;
  86.             while (q != p)
  87.             {
  88.                 count++;
  89.                 q = q->next;
  90.             }
  91.             q = p = head;
  92.             for (i = 0; i < count; i++)
  93.             {
  94.                 q = q->next;
  95.             }
  96.             while (p != q)
  97.             {
  98.                 p = p->next;
  99.                 q = q->next;
  100.             }
  101.             q->next = NULL;
  102.  
  103.             return 1;
  104.         }
  105.         else if (q->next == NULL)
  106.         {
  107.             return 0;
  108.         }
  109.         flag = !flag;
  110.     }
  111. }
  112.  
  113. void create(struct node **head)
  114. {
  115.     int c, ch;
  116.     struct node *temp, *rear;
  117.  
  118.     do
  119.     {
  120.         printf("Enter number: ");
  121.         scanf("%d", &c);
  122.         temp = (struct node *)malloc(sizeof(struct node));
  123.         temp->num = c;
  124.         temp->next = NULL;
  125.         if (*head == NULL)
  126.         {
  127.             *head = temp;
  128.         }
  129.         else
  130.         {
  131.             rear->next = temp;
  132.         }
  133.         rear = temp;
  134.         printf("Do you wish to continue [1/0]: ");
  135.         scanf("%d", &ch);
  136.     } while (ch != 0);
  137.     printf("\n");
  138. }
  139.  
  140. void release(struct node **head)
  141. {
  142.     struct node *temp = *head;
  143.     temp = temp->next;
  144.     while ((*head) != NULL)
  145.     {
  146.         free(temp);
  147.         temp = *head;
  148.         (*head) = (*head)->next;
  149.     }
  150. }

$ cc detectcycle.c 
$ ./a.out
Enter data into the list
Enter number: 1
Do you wish to continue [1/0]: 1
Enter number: 2
Do you wish to continue [1/0]: 1
Enter number: 3
Do you wish to continue [1/0]: 1
Enter number: 4
Do you wish to continue [1/0]: 1
Enter number: 5
Do you wish to continue [1/0]: 1
Enter number: 6
Do you wish to continue [1/0]: 1
Enter number: 7
Do you wish to continue [1/0]: 0
 
Identifying if a cycle exists.
Cycle detected in the linked list..

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

Here’s the list of Best Books in C Programming, Data-Structures and Algorithms

If you wish to look at programming examples on all topics, go to C Programming Examples.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.