Cycle start node of Cycle linked list

Question

I'm trying to implement a program for finding a starting node of circular linked list. My code is-

struct node
{
char data;
struct node *link;
} ;
char FindStartNode(struct node **q)
{
 struct node *r,*t;
 r = *q; 
 t = *q;
 while(t->link != NULL)
 {
 r = r->link;
 t = t->link->link;
 if(r == t)
 {
 break;
 }
 }
 if(t == NULL )
 return NULL;
 r = *q;
 while(r != t)
 {
 t = t->link;
 r = r->link;
 }
 return t->data;
}
int main()
{
struct node *p;
p = NULL;
char num;
Append(&p,'A');
Append(&p,'B');
Append(&p,'C');
Append(&p,'D');
Append(&p,'E');
Append(&p,'C');
Display(p);
 num = FindStartNode(&p);
printf("\nStarting node of the cycle linked list is:- %c",num);
_getch();
return 0;
}
int Append(struct node **q, char data)
{
struct node *r,*t;
r = (struct node *)malloc(sizeof(struct node));
r->data = data;
r->link = NULL;
if(*q == NULL)
 *q = r;
else
{
 t = *q;
 while(t->link != NULL)
 {
 t = t->link;
 }
 t->link = r;
 }
return 0;
}
int Display(struct node *q)
{
while(q != NULL)
{
 printf("%c\t",q->data);
 q = q->link;
}
return 0;
}

ths is my code. I'm not getting any value in return t->data part or I'm unable to find the start node of cycle ink list.Any help?

• Michael Burr: Is this code intended to determine if a list happens to be circle back to somewhere in the list (ie., that a node is linked in twice)? If so and assuming that you fix the NULL dereference that seems to be leading to this question, then it appears that you might get stuck in the last while loop with r endlessly chasing t.
• WhozCraig: Isn't the very idea of a "starting node" in a circular linked list somewhat... arbitrary? I thought they all could be a start-node. Or are you intended on finding the node that points to the one you have ? Are we to assume that *q has a pointer to some node, and the one you want is the one before it ?
• Hack Saw: What does that even mean, finding the starting node for a circular list? The code for creating the list ought to provide a pointer to an element, almost always the first one created. That's the entry point. After that, there is no real start or end, conceptually. That's why it's circular.
• WhozCraig: @HackSaw trust me, I'm sure the "huh?" was as loud on your side as it was here.
• Theocharis K.: I think the OP is trying to implement the Floyd's cycle-finding algorithm AKA the tortoise and the hare algorithm. You can read about it here.

Answer 1

 t = t->link->link; // t->link can be null 
 //so t = t->link->link can be a crash or illegal reference

Change the loop to:

 while(t != NULL)
 {
 r = r->link;
 t = t->link;
 if(t == NULL)
 break; // or return no circle
 else t = t->link;
 if(r == t)
 {
 break;
 }
 }

I have gone through your code. Comparing with the algorithm discussion here it seems to be OK. But you are returning a char why dont you return a pointer so that you can check if it is NULL or not. In case it is not null then issue pt->tada. This makes more sense.

I checked you code it seems you are not implementing circular linked list correctly in Append(). I am providing you with a working implementation below. See how I modified Append()

#include <stdio.h>
#include <stdlib.h>
struct node
{
char data;
struct node *link;
} ;
char FindStartNode(struct node **q)
{
 struct node *r,*t;
 r = *q;
 t = *q;
 while(t->link != NULL)
 {
 r = r->link;
 t = t->link->link;
 if(r == t)
 {
 break;
 }
 }
 if(t == NULL )
 return NULL;
 r = *q;
 while(r != t)
 {
 t = t->link;
 r = r->link;
 }
 return t->data;
}
int Append(struct node **q, char data);
int main()
{
struct node *p;
p = NULL;
char num;
Append(&p,'A');
Append(&p,'B');
Append(&p,'C');
Append(&p,'D');
Append(&p,'E');
Append(&p,'C');
//Display(p);
 num = FindStartNode(&p);
printf("\nStarting node of the cycle linked list is:- %c\n",num);
//_getch();
return 0;
}
int Append(struct node **q, char data)
{
struct node *r,*t, *startOfcycle=NULL;
r = (struct node *)malloc(sizeof(struct node));
r->data = data;
r->link = NULL;
if(*q == NULL)
 *q = r;
else
{
 t = *q;
 while(t->link != NULL)
 {
 if(t->data == data)
 startOfcycle = t;
 t = t->link;
 }
 if(startOfcycle == NULL)
 t->link = r;
 else {// there is a cycle point to the start of cycle
 t->link = startOfcycle;
 free(r);
 }
 }
return 0;
}
int Display(struct node *q)
{
while(q != NULL)
{
 printf("%c\t",q->data);
 q = q->link;
}

Please note that Display function is also wrong as runs an infinite loop of the linked list is circular. I have not modified it since it is not relevant to you question. Thanks.

• Amit_T: yeah, you are right I'm facing same problem but how can i ignore that?
• hmatar: Please look at my code I have added appropriate portion of code to modify.
• Amit_T: In return t->data ,I'm not getting any value.it should return the start node.why so?
• Hack Saw: Oh, no, t->data ought not give you back the starting node, only link might do that, unless you stored the starting node pointer into the data of a node.
• Amit_T: but before return t->data , I tried to print the value of t->data within that function, but that is also not showing any value.

Answer 2

...

 p = NULL;
 char num;
 Append(&p,'A');

...

You are trying to assign to NULL, which Append handles, but you are doing it repeatedly, which means you won't make a list, just a bunch of dangling nodes.

You need to make one node to start, outside of append, as your seed node, and pass that in.