Data structure

Question

what should be the statement at A

Comments

q!=NULL

---

Floyd’s Cycle-Finding Algorithm
This is the fastest method. Traverse linked list using two pointers.  Move one pointer by one and another pointer by two.  If these pointers meet at some node then there is a loop.  If pointers do not meet then linked list doesn’t have the loop.

Reference: https://www.geeksforgeeks.org/detect-loop-in-a-linked-list/

Answer 1

It will run until q  is actually at null.

hence A : q!=NULL

How ?

Let us take 3 nodes in a link list with no looping. nodes are A-->B-->C.

initially head is at A.

p=A

q=B.

Inside the loop,

it will increment p. hence now p = B.

next condition is

if(q->next)

   q = q->next->next;

else

   q= q->next.

Hence q->next = B->next = C it is true.

Hence q = q->next->next

q = NULL.

At this point no loop will be detected and hence code should be stop.

Hence condition A = q!=NULL.