Linked list loop detection in Java
This is a classic interview question.  At this point, I think it measures more whether you've been to many interviews than whether you can think creatively algorithmically while on a job interview.  Anyway,

public class Node {
  public Node next = null;
  public Node() {}
  public Node(Node n) { next = n; }
  public boolean hasNext() { return next != null; }
  public boolean hasLoop() {
    Node n = this, n2 = this;
    while (n.hasNext()) {
      n = n.next;
      if (n == n2) return true;
      if (!n.hasNext()) return false;
      n = n.next;
      if (n == n2) return true;
      n2 = n2.next;
    }
    return false;
  }
}


(Not compiled, but you get the idea.  I think getters/setters for next is overkill, given that the whole point is to manipulate the field at a low level, given this data structure.)

This uses constant space; since n travels twice as fast as n2, if there is a loop, both n and n2 will get caught at it and n will overtake n2 from behind (after a maximum number of steps equal to twice (lead-in plus loop length)).  Otherwise, n will reach the end and we're done.