findHead

gistfile1.java

Node findHead(Node start) {
  int tortoiseSpeed = 0, hareSpeed = 0;
  Node tortoise, hare;
 
  if (start == null)
    return start;
 
  for (tortoiseSpeed = 0; true; tortoiseSpeed = hareSpeed + 1) {
    if (start.jump(tortoiseSpeed+1) == null)
      return null;
    
    for (hareSpeed = 1; tortoiseSpeed >= 0; hareSpeed++, tortoiseSpeed--) {
      tortoise = start.jump(tortiseSpeed);
      hare = tortoise.jump(hareSpeed);
      if (tortoise == hare)
        return hare;
    }
  }
}