single linked list에서 루프를 찾는 방법

- 오늘의 퀴즈입니다.
1) single linked list에서 루프가 존재하는지를 구하는 방법

hint) 거북이와 토끼의 경주에서 산꼭대기를 향해서 뛰어가지 않고, 트랙을 돌고 있다면?

답)
거북이와 토끼는 처음 만나서 경주를 하게 됩니다.
토끼는 육상 선수여서 그런지 엄청빠른 속도로 달릴 수가 있지요. 그에 비해 거북이는 엉그적 엉그적 느리게 걸어갑니다.

출발 소리를 들리고 토끼가 잽싸게 뛰쳐 나가죠. 이 놈의 속도를 측정하니 거북이의 두배나 빨랍답니다. 이에 비해서 거북이는 세월아 내월아 천천히 걸어가고 있었어요.

그런데 사실 토끼와 거북이의 경주는 산을 향해서 달리고 있었던게 아니었어요.
산꼭대기로 난 길이라고 생각했지만 산 주위를 계속 돌고 있는 길이었죠.
기억력이 나쁜 토끼는 자신이 산 주위를 돌고 있다는 것을 이해하지 못했어요.

언제까지?

거북이가 나타날 때까지 !! ㅎㅎ

// Best solution
function boolean hasLoop(Node startNode)
{
  Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next())
  {
     if (slowNode == fastNode1 || slowNode == fastNode2) return true;
  slowNode = slowNode.next();
  }
return false;
}

이 알고리즘의 원문은

"Floyd's Cycle-Finding Algorithm" as published in "Non-deterministic Algorithms" by Robert W. Floyd in 1967. It is also called "The Tortoise and the Hare Algorithm".