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

1. 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;

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. 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 r=false;
struct list *current=NULL;

{
{
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. 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');
}

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.