Detecting a Cycle in Linked List

How do you detect a cycle in a linked list? A cycle occurs if one node points back to a previous node in the list. You could solve this by using an intermediary data structure, but a more efficient algorithm is Floyd's "hare and tortoise" algorithm.

The idea is to have two iterators; the hare and the tortoise. The hare runs along the list faster than the tortoise and if the list has a cycle, the hare will eventually overtake the tortoise. The following code illustrates the algorithm:

public boolean hasCycle(Node root){
  Node tortoise = root;
  Node hare = tortoise.next;

  while (hare != tortoise) {
    // tortoise moves one place
    tortoise = tortoise.next;

    // hare moves two places
    hare = hare.next;
    if (hare != null) {
      hare = hare.next;
    }

    if (tortoise == null || hare == null) {
      // end of list, no cycles
      return false;
    }
  }
  return true;
}

(This is an interview question.)