title: How to detect a loop in a linked list?
body: <p>Say you have a linked list structure in Java.  It's made up of Nodes:</p>
  
  <pre><code>class Node {
      Node next;
      // some user data
  }
  </code></pre>
  
  <p>and each Node points to the next node, except for the last Node, which has null for next.  Say there is a possibility that the list can contain a loop - i.e. the final Node, instead of having a null, has a reference to one of the nodes in the list which came before it.</p>
  
  <p>What's the best way of writing</p>
  
  <pre><code>boolean hasLoop(Node first)
  </code></pre>
  
  <p>which would return <code>true</code> if the given Node is the first of a list with a loop, and <code>false</code> otherwise?  How could you write so that it takes a constant amount of space and a reasonable amount of time?</p>
  
  <p>Here's a picture of what a list with a loop looks like:</p>
  
  <p><img src="https://i.stack.imgur.com/irw1S.jpg" alt="alt text"></p>