< 문제 > linked list가 a - b - c - d - e - c - d - e - c - d - e ... 같이 연결되어 있을때, 순환이 시작되는 지점을 찾아라.
[사진 1 : 위와 같이 연결 되어 있을 때, 순환이 시작되는 지점의 원소를 return 하면 된다.
이 문제는 2칸씩 움직이는 fast pointer 와 1칸씩 움직이는 slow pointer의 위치를 보면서 생각하면 쉽게 풀 수 있다.
1. fastPointer 는 2칸씩 움직이고, slowPointer는 1칸씩 움직인다고 하자.
2. 각각 순환되지 않는 부분 m 길이, 순환되는 부분 n 길이를 가진다고 하자.
fastPointer가 2m, slowPointer가 m 만큼 움직였으면, fastPointer는 순환되는 지점에서 m - n * k ( k는 0이상의 정수, 전체 2m 만큼 움직였는데, m 만큼 직선 거리를 이동했으므로 2m - n * k - m ) 만큼 이동해 있을 것이다.
3. 이를 a 라고 하자. ( a = m - n*k )
이 때, fastPointer와 slowPointer가 만나기 위해서는 n - a 만큼 slowPointer가 이동해야 한다. ( fastPointer와 slowPointer사이의 거리는 1번 이동할 때 1만큼 줄어드는데, n - a 만큼 떨어져 있으므로, )
4. 따라서 처음으로 fastPointer와 slowPointer가 만나는 부분은 순환이 시작하는 부분에서 a 만큼 떨어진 부분이다. 즉, 1의 조건대로 움직이게 해서 처음 만나는 부분이 순환이 시작하는 곳에서 a 만큼 떨어진 부분 ( n - a ) 이라는 것이다.
5. 이제 slowPointer를 처음으로 보내고, slow와 fastPointer 2 포인터 모두 1칸씩 움직인다고 해보자. m 길이를 움직였을 때, fast는 n - a의 위치에서 m 만큼 움직였고, slow는 0에서 m만큼 움직였다.
6. slow는 순환이 시작하는 부분에 서있는 것은 자명하다. fast는 n-a + m 이므로, 3에 의해서 n - m + n*k + m 의 위치, 즉 n * (k +1)의 위치에 서있으므로, 시작하는 부분이라는 것을 증명 할 수 있다.
7. 따라서 처음으로 만나는 부분에서 속도를 1로 바꾼 뒤 다시 처음으로 만나는 지점이 순환 시작점이다.
