4 ms·

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. Wh

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; } :)

eps 10y ago
An implementation-specific hack. Neat, but hack nonetheless.
huhtenberg 10y ago
Hacky, trashes CPU cache, the code itself is on a sloppy side and, most importantly, it lacks the elegance of the original solution. So I beg to differ, it's not really "better" by any metric.
- sherincall 10y ago
  It was tongue-in-cheek (see the smiley face), your critiques are all spot on, but there is one thing where it is objectively better: Tortoise and hare can only detect that a cycle exists. This hack will tell you exactly which node the cycle starts on. That means that if you want to e.g. repair a list, you can just cut that last link and set it to either null or root. Granted, this wasn't the original problem.
  - bfors 10y ago
    Tortoise and hare can actually tell you which node the cycle starts on. 1 -> 2 -> 3 -> 4 -> 5 -> 6 ^ | |______________| Step: 0 1 2 3 4 Tortoise: 1 2 3 4 5 Hare: 1 3 5 3 5 <- pointers reference same node, cycle exists Then create another tortoise pointer at the head, iterate until both tortoises point to the same node. Step: 0 1 2 Tortoise: 5 6 3 Tortoise2: 1 2 3 <-cycle starts at 3

eps 10y ago

An implementation-specific hack. Neat, but hack nonetheless.

huhtenberg 10y ago

Hacky, trashes CPU cache, the code itself is on a sloppy side and, most importantly, it lacks the elegance of the original solution. So I beg to differ, it's not really "better" by any metric.

sherincall 10y ago
It was tongue-in-cheek (see the smiley face), your critiques are all spot on, but there is one thing where it is objectively better: Tortoise and hare can only detect that a cycle exists. This hack will tell you exactly which node the cycle starts on. That means that if you want to e.g. repair a list, you can just cut that last link and set it to either null or root. Granted, this wasn't the original problem.
- bfors 10y ago
  Tortoise and hare can actually tell you which node the cycle starts on. 1 -> 2 -> 3 -> 4 -> 5 -> 6 ^ | |______________| Step: 0 1 2 3 4 Tortoise: 1 2 3 4 5 Hare: 1 3 5 3 5 <- pointers reference same node, cycle exists Then create another tortoise pointer at the head, iterate until both tortoises point to the same node. Step: 0 1 2 Tortoise: 5 6 3 Tortoise2: 1 2 3 <-cycle starts at 3