SLL – Singly Linked List.

We all know the obvious one:

List *ptr1;

if (!curPtr) return 1; //An empty list is circular or non-circular?

ptr1 = curPtr->next;

while (ptr2 != NULL) {

if(ptr1 == ptr2) return 0;

ptr2 = ptr2->next;

}

return 1;

In this case, if the list has n elements and the list is circular, then there will be **n **pointer dereferences.

I have another one in mind: instead of traversing **ptr1** in single steps, traverse it in double steps – so we will loop over fast:

ptr1=curPtr->next;

while(ptr1 != NULL) {

if(ptr1 == curPtr || ptr1->next == curPtr) return 0;

if(ptr1->next) ptr1 = ptr1->next->next;

else ptr1 = NULL;

}

return 1

Although I wonder if this is any better than the above one. At best, this is some loop unrolling I think. 🙂

I came to know about another mechanism. Instead of having a single pointer, you keep two pointers. You make the second pointer traverse fast – that is instead of walking past single node, you walk past two nodes at a time – the basic idea being if it is a circular list, you will quickly loop over and come back to the slow moving pointer. Even if it is not a circular pointer, you will fall off the list quickly.

The interesting thing here is analysis – first question to ask is – **will they meet eventually?**, because it may happen that the fast walking pointer might skip the slow walking pointer in a hurry. So this needs some proof that both will meet.

So here is such an argument that they will eventually meet: after the slow and the fast pointers (so to speak) are initialized to i and i+1, it will take exactly **n-1** iterations for them to meet. To make sense of it, consider this: after **n-1 **iterations, the slow pointer will be at **(i+n-1)%n th** position – which is equivalent to **(i-1)%n**. The fast pointer will be at:

(i+1 + 2(n-1))%n

= (i+1+2n -2)%n

= (i-1+2n)%n

= (i-1)%nth position.

Hence after **n-1 **iterations, both will be at **(i-1)%n** th position which means they both meet. But, this is slower than the alternative where we keep the first pointer static and move only the second pointer.