토끼와 거북이 알고리즘 Floyd's Tortoise and Hare algorithm

 
linked list 에서 이용할 수 있는 알고리즘으로 2개의 포인터를 사용한다.
하나는 한번에 2칸씩 이동, 하나는 하나씩 이동한다.
 
이 알고리즘을 통해 linked list에 loop강 없다면 해당 리스트의 중간지점을 찾는다거나 
linked list안에 loop가 있는지 찾을 수 있다.
왜냐하면 loop가 있다면 두개의 노드는 언젠가는 만나게 되기 때문이다.
 
그리고 또 한가지 loop의 시작점을 알 수 있다.
어떻게 하느냐
두개의 노드를 2칸씩(fast pointer) 1칸씩(slow pointer) 이동시키다보면 둘은 만나게 된다.
그 시점부터 slow pointer를 head로 이동시켜 한칸씩 이동시키고 fast는 만나게 되는 지점부터 한칸씩 이동시킨다.
그렇게 서로 다른 지점에서 한칸씩 이동하다보면 또 만나게 되는데, 그 지점이 loop가 시작되는 곳이다.
어떻게 항상 이런식으로 loop의 시작점을 찾을 수 있는지 증명할 수 있을까?
 
증명

대충 이렇게 loop가 있는 linked list 가 있다.
slow pointer가 meeting point에 다다르기까지의 거리가 x+y  
fast pointer는 slow 보다 2배 빠르니까 2(x+y)
이다.
 
2(x+y) 를 다른식으로 표현하면 x+y+k*L 이 될 수 있다.
x+y는 meeting point 까지 처음부터 한칸씩 이동했을때 거리
k는 loop안에서 반복하는 횟수, L은 loop의 길이이다.
 

2(x+y) = x+y+k*L 
이 식을 풀어나가다보면 결국
x % L = z
라는 결과가 도출되는데 
이는 x의 거리를 loop의 길이로 나눴을때 남는 거리와
loop안의 meeting point 부터 시작점까지의 거리가 같다는 것을 의미한다.

즉 시작점과 meeting point 에서 한칸씩 이동하면 결국 둘은 loop의 시작점에서 만난다는 것을 뜻한다.