Thread: 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

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;
}

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.