@ Linked List

Given a linked list, find whether it has a loop or not.

Clarification: do we know the number of nodes in the linked list?

If yes: Lets say it has n nodes. An O(n) solution is traverse the list seeking the next node every time for n-1 times. If, the "next" pointer now points to NULL, then the linked doesn't have a cycle, else it has one .

Is there some thing smarter?

No, the no. of nodes is not given....ya, there is something smarter.

I hope you are not trying to tag/id visited nodes!

no tagging is needed.. think in terms of relative velocity ...

any ideas...

Take 2 pointers.. p1 and p2...

make p1 traverse the list at the rate of one node / cycle
and p2 traverse the list at the rate of 2 nodes / cycle.

If p1 and p2 match then there is a loop , otherwise not.. make sure you check for NULL (termination condition)

say head of the list is root.

bool loop = FALSE;
p1 = p2 = root;

while ( p1 && p2->next)
{

p1 = p1->next;
p2 = p2->next->next;

if (p1 == p2)
{
loop = TRUE;
break;
}

}