5 ms·
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
by DDR0 10y ago
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 duplicate.
There's a way to do it in O(1) space, though.
If you start off two runners in the list, and each "step" move one twice and the other only once, if there's a loop they will eventually run into each other and be processing the same element. Simple, elegant, and nothing I'd have ever thought of. :)
- simooooo 10y agoWell... that's rather Ingenious.
- eps 10y agoThis can also be used to determine the period of Linear Congruential PRNGs, i.e those in form of X(n+1) = (A * X(n) + B) mod C which happens to be what many stdlib versions of rand() are. https://en.wikipedia.org/wiki/Linear_congruential_generator https://en.wikipedia.org/wiki/Linear_congruential_generator
- mavelikara 10y agoThis algorithm is popularly known as "Floyd's tortoise and the hare algorithm".
- rosstex 10y agoHere's a visual representation of it: https://visualgo.net/cyclefinding https://visualgo.net/cyclefinding Really cool!
- deleted 10y ago[deleted]
- sherincall 10y agoI 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 agoAn implementation-specific hack. Neat, but hack nonetheless.
- huhtenberg 10y agoHacky, 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 agoIt 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 agoTortoise 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
- pkd 10y agoThis one is extremely popular in the interviewing circles thanks to CTCI.
- csmattryder 10y agoJust ran it through on the office whiteboard, colour me impressed, really novel! Did have to remind myself to start the double-jumper off before the single-pointer to prevent a short-circuit, but that's a great solution to cyclical lists. Where did you learn about this?