Linked List

Question

Consider the following program

struct node
    {
        int value;
        Node *next;
    }
    boolean fun(Node *head)
    {
        Node *a,*b;
        a=head;
        if(a==NULL)
        return TRUE;
        b=a->next;
        while(b!=NULL && b!=a)
        {
            b=b->next;
            if(b==NULL)
            return TRUE;
            b=b->next;
            a=a->next;
        }
        return(b==NULL);
    }

Is the following code return this?

a)

Comments

No I don't think so

At end b points to null

the reason is that in figure it is shown that last node's next field point's to the node whose address is currently held by pointer a but in the code we have never written such line

Modified code can be

 boolean fun(Node *head)
    {
        Node *a,*b,*c;

        a=head;
        if(a==NULL)
        return TRUE;
        b=a->next;
        while(b!=NULL && b!=a)
        {  
            c=b;
            b=b->next;
            if(b==NULL)
            {
            c->next=a;/* bcz here c is pointing to last node and whose next field we want        to point to node pointed by pointer a*/
            return TRUE;
            }
           b=b->next;
            a=a->next;
        }
        return(b==NULL);
    }

---

write elaborate where is problem

Such type of ans not required

If u understand elaborately answer it

---

Sorry for poor formating !
 
boolean fun(Node *head)
    {
        Node *a,*b,*c;

        a=head;
        if(a==NULL)
        return TRUE;
        b=a->next;
        while(b!=NULL && b!=a)
        {  
            c=b;
            b=b->next;
            if(b==NULL)
            {
            c->next=a;/* bcz here c is pointing to last node and whose
             next field we want to point to node pointed by pointer a*/
            return TRUE;
            }
           b=b->next;
            a=a->next;
        }
        return(b==NULL);

---

@akb

I am very sorry, that still not getting, what c is doing actually

I gone throgh ur code by diagram  still not getting

Could u plz explain in some words?

---

Actually I miss interpret your question I thought that you were asking what modification to be done in code so that  the linked list will satisfy  the property as given in figure but by reading habib's answer now it is clear that this code actually finds the cycle in the list.

---

but ans given this loop not found by the code

Answer 1

Basically the given code attempts to find the cycle in the given linked list if at all it exists.

So if we take the instance of linked list as shown in the diagram in the question , there is no node whose next points to NULL , as we can see last node is connected to middle node and hence the cycle exists.

So the condition of the while loop : 

 while(b!=NULL && b!=a)

checks if b is NULL or 'b' is same as 'a' meaning that the cycle is detected in the linked list , thereby the loop terminates.

The final line : 

 return(b==NULL)

will return if b is NULL which is not the case here as it is pointing to valid node in the linked list . Hence b == NULL will return 0 meaning that b == NULL truth value is false actually. [The loop terminated because b == a happened in the middle node of the linked list ]

Hence the return value of the function will be 0.

Comments

@Habib

yes we are searching loop.

I have got that b is pointing next node of a

And b pointer incrementing twice than a pointer.

So, in 2nd iteration of while loop b point the same node, which a points too.

So, this diagram satisfies the program

right?