<story><title>Ask HN: What are your favorite algorithms?</title><text>Post any algorithms you think are cool, inventive, or useful.
PDF links or blog posts are appreciated.&lt;p&gt;My current favorite is SWIM.
https:&amp;#x2F;&amp;#x2F;www.cs.cornell.edu&amp;#x2F;~asdas&amp;#x2F;research&amp;#x2F;dsn02-swim.pdf</text></story><parent_chain><item><author>DDR0</author><text>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&amp;#x27;s a 9-shaped linked list? You&amp;#x27;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&amp;#x27;ve found a duplicate.&lt;p&gt;There&amp;#x27;s a way to do it in O(1) space, though.&lt;p&gt;If you start off two runners in the list, and each &amp;quot;step&amp;quot; move one twice and the other only once, if there&amp;#x27;s a loop they will eventually run into each other and be processing the same element. Simple, elegant, and nothing I&amp;#x27;d have ever thought of. :)</text></item></parent_chain><comment><author>sherincall</author><text>I like my solution better:&lt;p&gt;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:&lt;p&gt;&lt;pre&gt;&lt;code&gt;    bool containsCycle(node_t *root)
    {
        node_t *p = root;
        bool ret = false;
        if (!root) return false; &amp;#x2F;&amp;#x2F; Empty list

        while (p-&amp;gt;next &amp;amp;&amp;amp; !ret)
        {
            if ((uintptr_t)p-&amp;gt;next &amp;amp; 1)
            {
                ret = true;
                break;
            }
            node_t *q = p-&amp;gt;next;
            p-&amp;gt;next = (uintptr_t)p-&amp;gt;next | 1;
            p = q;
        }
    
        &amp;#x2F;&amp;#x2F; Reset all pointers
        p = root;
        while (p-&amp;gt;next &amp;amp;&amp;amp; ((uintptr_t)p-&amp;gt;next &amp;amp; 1))
        {
            p-&amp;gt;next = (uintptr_t)p-&amp;gt;next &amp;amp; ~1;
            p = p-&amp;gt;next;
        }
        return ret;
    }
&lt;/code&gt;&lt;/pre&gt;
:)</text></comment>
<story><title>Ask HN: What are your favorite algorithms?</title><text>Post any algorithms you think are cool, inventive, or useful.
PDF links or blog posts are appreciated.&lt;p&gt;My current favorite is SWIM.
https:&amp;#x2F;&amp;#x2F;www.cs.cornell.edu&amp;#x2F;~asdas&amp;#x2F;research&amp;#x2F;dsn02-swim.pdf</text></story><parent_chain><item><author>DDR0</author><text>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&amp;#x27;s a 9-shaped linked list? You&amp;#x27;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&amp;#x27;ve found a duplicate.&lt;p&gt;There&amp;#x27;s a way to do it in O(1) space, though.&lt;p&gt;If you start off two runners in the list, and each &amp;quot;step&amp;quot; move one twice and the other only once, if there&amp;#x27;s a loop they will eventually run into each other and be processing the same element. Simple, elegant, and nothing I&amp;#x27;d have ever thought of. :)</text></item></parent_chain><comment><author>eps</author><text>This can also be used to determine the period of Linear Congruential PRNGs, i.e those in form of&lt;p&gt;&lt;pre&gt;&lt;code&gt;    X(n+1) = (A * X(n) + B) mod C
&lt;/code&gt;&lt;/pre&gt;
which happens to be what many stdlib versions of rand() are.&lt;p&gt;&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Linear_congruential_generator&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Linear_congruential_generator&lt;/a&gt;</text></comment>