Thread: Finding out circular linked list example.. Query with respect to implementation.

  1. #1
    Registered User
    Join Date
    Mar 2008
    Location
    India
    Posts
    133

    Finding out circular linked list example.. Query with respect to implementation.

    Hi All ,

    I have below program , which finds out whether the given linked list is circular linked list or not.

    Code:
    Int containsLoop (listptr head)
    {
    	Listptr  *ptr1, *ptr2;
    	
    	Ptr2 = head;
    	If (head != NULL) 
      ptr1 = ptr2>next;
    
    while ( ptr1!=ptr2 && ptr1 != NULL)
    {
    	Ptr2 = ptr2->next;
    	If (ptr1->next != NULL)
    	  Ptr1 =ptr1->next->next;
    	Else
    	  Return (0);
       }
         If (ptr1 == ptr2)
    	Return (1);
        Else
    	Return (0);
    }
    
    }
    The query here is , why ptr1 should also traverse ?. I think ptr1 will be at same point and ptr2 will traverse and once ptr1 and ptr2 are same it confirms circular linked list.

    Thanks

  2. #2
    Registered User
    Join Date
    Apr 2017
    Location
    Iran
    Posts
    101
    Hi,

    Here is my try:
    Code:
    #include <stdlib.h>
    #include <stdio.h>
    #include <stdbool.h> 
    
    void non_cir(void);
    void cir_ll (void);
    
    struct list
    {
        unsigned data;
        struct list *next;
    };
    
    void simple_err(const char *const str)
    {
        fprintf(stderr,"%s\n",str);
        exit (EXIT_FAILURE);
    }
    
    bool contains_cir(struct list * head)
    {
        bool r=false;
        struct list *current=NULL;
        
        if(head==NULL)
            simple_err("head is NULL");
        
        for(current=head->next; current->next!=NULL; current=current->next)
        {
            if(current==head)
            {
                r=true;
                break;
            }
        }
        
        return r;
    }
    
    int main(void)
    {
        //printf("a3\n");
        non_cir();
        cir_ll();
        
        return EXIT_SUCCESS;
    }
    
    void non_cir(void)
    {
        static struct list nc[3]={{0,nc+1},{1,nc+2},{3,NULL}};
        if(!contains_cir(nc))
            printf("%s is not circular.\n",__FUNCTION__);
        else
            simple_err("problem in non_cir.");
        
        return;
        
    }
    
    void cir_ll (void)
    {
        static struct list cll[2]={{0,cll+1},{1,cll}};
        
        if(contains_cir(cll))
            printf("%s is circular.\n",__FUNCTION__);
        else
            simple_err("problem in cir_ll.");
            
        return;
    }

  3. #3
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    In Floyd's cycle-finding algorithm (a.k.a., the tortoise and the hare algorithm) one pointer moves twice as fast as the other. The fast pointer will either hit a NULL pointer (meaning no cycle) or it will wrap around and eventually become equal to the slow pointer, indicating a cycle.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    #define LISTSIZE   37
    #define CONNECT_TO 15   // must be >= 1 && < LISTSIZE
    
    typedef struct List List;
    
    struct List {
        int n;
        List *next;
    };
    
    List *lst_prepend(List *lst, int n) {
        List *node = malloc(sizeof *node);
        if (!node) { perror("malloc"); exit(EXIT_FAILURE); }
        node->n = n;
        node->next = lst;
        return node;
    }
    
    void lst_print(List *lst) {
        for ( ; lst; lst = lst->next)
            printf("%d ", lst->n);
        putchar('\n');
    }
    
    void lst_print_with_limit(List *lst, int limit) {
        for (int i = 0; i++ < limit && lst; lst = lst->next)
            printf("%d ", lst->n);
        putchar('\n');
    }
    
    int containsCycle(List *head) {
        List *pslow = head, *pfast = head;
        while (pfast && pfast->next) {
            pslow = pslow->next;
            pfast = pfast->next->next;
            if (pfast == pslow)
                return 1;
        }
        return 0;
    }
    
    void create_cycle(List *lst, int connect_to) {
        List *tail = lst;
        if (tail) {
            // find the tail and "connect_to" nodes
            List *node = NULL;
            for (int i = 1; tail->next; tail = tail->next, i++)
                if (i == connect_to)
                    node = tail;
            // connect them
            tail->next = node;
        }
    }
    
    int main() {
        List *lst = NULL;
    
        for (int i = LISTSIZE; i > 0; i--)
            lst = lst_prepend(lst, i);
        lst_print(lst);
    
        printf("%s\n\n", containsCycle(lst) ? "cycle" : "no cycle");
    
        create_cycle(lst, CONNECT_TO);
    
        lst_print_with_limit(lst, LISTSIZE * 3);
    
        printf("%s\n\n", containsCycle(lst) ? "cycle" : "no cycle");
    
        return 0;
    }
    BTW, the "code" you posted is total garbage. This is your 125th post, and that's what you give us? It's unconscionable.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Wut is wrong in this circular list implementation ?
    By rajarshi in forum C Programming
    Replies: 10
    Last Post: 11-24-2011, 10:17 AM
  2. circular linked->list help
    By The Brain in forum C++ Programming
    Replies: 8
    Last Post: 10-21-2004, 11:12 AM
  3. Circular linked list
    By campermama in forum C++ Programming
    Replies: 7
    Last Post: 06-15-2004, 11:53 AM
  4. Circular Linked list ....
    By yescha in forum C Programming
    Replies: 1
    Last Post: 11-17-2001, 03:41 AM
  5. Again, Circular Linked list ???
    By yescha in forum C Programming
    Replies: 2
    Last Post: 11-16-2001, 08:35 PM

Tags for this Thread