Advertisement
Guest User

Cyclic or Acyclic Linked List

a guest
Jun 28th, 2011
146
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.81 KB | None | 0 0
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3.  
  4. typedef struct Node{
  5.     struct Node *next;
  6.     int data;
  7. }Node;
  8.  
  9. int cyclicOrNot(Node *head){
  10.     Node *fastPtr=head;
  11.     Node *slowPtr=head;
  12.    
  13.     if (!fastPtr)
  14.         return 0;
  15.    
  16.     int i;
  17.     for(i=0;;i++){
  18.         fastPtr=fastPtr->next;
  19.         if (i%2)
  20.             slowPtr=slowPtr->next;
  21.            
  22.         if (!fastPtr)
  23.             return 0;
  24.        
  25.         if (fastPtr==slowPtr)
  26.             return 1;
  27.     }
  28. }
  29.  
  30. Node *createList(int elements, int cyclic){
  31.     if (elements<1)
  32.         return NULL;
  33.        
  34.     Node *head=(Node *)malloc(sizeof(Node *));
  35.     head->data=0;
  36.     Node *cur=head;
  37.    
  38.     int i;
  39.     for (i=1;i<elements;i++){
  40.         cur->next=(Node *)malloc(sizeof(Node *));
  41.         cur=cur->next;
  42.         cur->data=i;
  43.     }
  44.     if (cyclic){ //cyclic case
  45.         int elem;
  46.         if (cyclic<=elements)
  47.             elem=0;
  48.         else
  49.             elem=cyclic;
  50.            
  51.         //find the element and make your last node point back to it
  52.         Node *backElem=head;
  53.         for(i=0;i<elem;i++)
  54.             backElem=backElem->next;
  55.         cur->next=backElem;        
  56.     }      
  57.     else //acyclic case
  58.         cur->next=NULL;
  59.        
  60.     return head;
  61. }
  62.  
  63. void printList(Node *head){
  64.     Node *cur=head;
  65.    
  66.     //to prevent infinite loop
  67.     int count=0;
  68.     printf("List:");
  69.     while (cur){
  70.         printf("%d,",cur->data);
  71.         cur=cur->next;
  72.         count++;
  73.         if(count>10){ printf("\n"); return;}
  74.     }
  75.     printf("\n");
  76. }
  77.  
  78. int main(){
  79.    
  80.     //create an acyclic list and test it
  81.     Node *head=createList(5,0);
  82.     printList(head);
  83.    
  84.     if (cyclicOrNot(head))
  85.         printf("Error: the function didn't correctly identify an acyclic list\n");
  86.     else
  87.         printf("Success: the function correctly identified an acyclic list\n");
  88.        
  89.     //create a cyclic list and test it
  90.     head=createList(5,1);
  91.     printList(head);
  92.    
  93.     if (cyclicOrNot(head))
  94.         printf("Success: the function correctly identified a cyclic list\n");
  95.     else
  96.         printf("Error: the function didn't correctly identify a cyclic list\n");
  97.     return 0;
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement