Finding Whether a SLL is circular or not.

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)%n th 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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s