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

@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?