Given the head of a linked list, how do you determine if it loops? eg, an l-shaped list is easy to determine - you simply process each element in the list until you find one without a subsequent element. But what if it's a 9-shaped linked list? You'll never run out of elements, so the best you could seem to do would be to store a reference to each element and check against all references to see if you've found a dupl…
I like my solution better:
The list node contains a pointer and some data, most likely another pointer, or a primitive type, or a struct of primitive types. Which means, that on all modern systems, a list node is aligned to at least 16 bits, much more likely 32 bits. That means that the pointer to the node always has the last bit set to zero. So:
bool containsCycle(node_t *root)
{
node_t *p = root;
bool ret = false;
if (!root) return false; // Empty list
while (p->next && !ret)
{
if ((uintptr_t)p->next & 1)
{
ret = true;
break;
}
node_t *q = p->next;
p->next = (uintptr_t)p->next | 1;
p = q;
}
// Reset all pointers
p = root;
while (p->next && ((uintptr_t)p->next & 1))
{
p->next = (uintptr_t)p->next & ~1;
p = p->next;
}
return ret;
}