Thread: Circle in linked list

Question asked by visitor manish jaiswal

What is the procedure to be applied for finding whether there is any circle formed in a linked list?

plz keep in mind there is a bulk of elements in linked list, so complexity must be negligible.

basic concept is that if a particular node is linked to any of the previous nodes,then it forms a circle.
even a single node with a link pointing to itself is a circle length one.

thus by checking whether the link field of the last node is linked to the header node , you can find whether a circle is present or not.

You can have two pointers p,q pointing to the header node...Inside a while loop you move the second pointer by two nodes and first pointer by one node...if loop exists,definitely the two pointers will meet each other,so p==q condition gets satisfied...This method not only finds the loop formed in the header node but also finds the loop formed in any other nodes...The code as follows:-

{
struct node *p=header;
struct node *q=header;
int k=0;
while(q->next!=null && !k)
{
p=p->next;
q=q-next->next;
if(p==q)
k=1;
}
if(k)
printf("loop exists")
else
printf("no loop");
}

if there is no loop then q will reach null before p...If there is no loop,the loop will set k as 1 at one time,I think this will work for all...


regards,
rms...

I know in c / c++, a function(module) called by itself more than once is called function recursion. But i want to know the actual process i.e how data is executing inside and how display occur by giving any authentic example.. Thanx

For recursive function calls, every time the function is called, it get loaded onto STACK. Consider the below example code for finding factorial of a number using recursion.
/*****************/
int main(int argc, char* argv[])
{
int num = 5;

printf("Factorial!! = %d\n", fact(num));

return 0;
}

int fact(int num)
{
if((num == 1) || (num == 1))
{
return 1;
}
else
{
return (num * fact(num-1));
}
}
/**********************/

Below is the CALL STACK for factorial of number 5
/*********************/
2 * fact(int 1) line 21
3 * fact(int 2) line 25 + 12 bytes
4 * fact(int 3) line 25 + 12 bytes
5 * fact(int 4) line 25 + 12 bytes
fact(int 5) line 25 + 12 bytes
main(int 1, char * * 0x00910e80) line 12 + 9 bytes
/*********************/

Explaination: The evaluation shall be as per the stack behaviour(LIFO). For the 1st time when fact(num) is called, it will be loaded in stack. inside this function fact(num-1) is called as long as the else condition is satisfied. When num = 1 or num = 0 is satisfied, then evaluation starts and evaluation order will as shown above. Return Value from each stage is multiplied with previous stage and FINALLY returns to the MAIN function where factorial value is displayed.

Hope this is useful!!!!
--> Pavan Mustyala

Hi, This below code can be used to check for circle in the list. This is updated version for RMSECE's post. The number of iterations will reduce by 1 compared to that code since initially, 1st pointer points to HEAD node and 2nd pointer points to node next to HEAD. There by one iteration is reduced here. But in worst case, both methods results in same number of iterations.

void findCircleInList(LIST *pHead)
{
LIST *p = pHead;
LIST *q = pHead->pNext;
int k = 0;
int count = 0;

while(q != NULL && q->pNext!= NULL && !k)
{
p = p->pNext;
q = q->pNext->pNext;
if(p == q)
k = 1;
count++;
}
if(k)
printf("\n\nloop exists % d\n\n", count);
else
printf("\n\nno loop %d\n\n", count);
}