Hacker News Reader

Comment by DDR0 | Hacker News Reader

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. :)

View on HN

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

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

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.

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.

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

This algorithm is popularly known as "Floyd's tortoise and the hare algorithm".

This 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

Here's a visual representation of it:

https://visualgo.net/cyclefinding

Really cool!

Just 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?

This one is extremely popular in the interviewing circles thanks to CTCI.

Well... that's rather Ingenious.

Reply on news.ycombinator.com