루프 발견

2.8 문제 - 루프 발견

순환 연결리스트가 주어졌을때, 순환되는 부분의 첫째 노드를 반환 하는 알고리즘을 작성하라. 

순환 연결리스트란 노드의  next 포인터가 앞선 노드들 가운데 어느 하나를 가리키도록 설정되어 있는 변질된 방식

의 연결리스트를 의미한다.

입력:  A > B > C > D >E> C (앞에 나온 C와 같음) // 입력 0 > 1 > 2 > 3> 4> 5> 6> 7> 8> 9> 10 > 3

출력 : C                                                       // 출력 3

        
문제 해결 방법

1. 연결리스트에서 순환 구조의 유무 검사 

-탐색 속도가 다른 2개의 포인터를 이용.   (RUNNER 기법)

-SLOW: P만큼 나아갈때 1칸

-FAST: 2P만큼 나아간다 2칸

-이용해서 만나면 순환구조가 있다고 볼 수 있다.

-루프가 아닌부분의 크기를 K 라고 가정

-SLOW가 K만큼 움직여서 루프의 시작 부분에 도착하면

-FAST는 2K 만큼 나아감. -루프의 시작에서 K만큼 더 진입 

루프의 크기보다 K가 더 큰 값일 수 있어서 

K= MOD( K,  LOOP의 크기)= 3 % 8 =3 

(LOOP의 크기 - K )의 횟수 만큼 이동

결국 만나는 지점은 루프의 시작에서 K만큼 뒤쳐짐

둘이 만나면 순환 구조 유무 확인

2. 순환의 시작 부분을 찾는것

SLOW를 리스트의 시작지점으로 변경

FAST는 그대로 두고 속도는 같에 변경하고 출발

루프의 시작지점에서 충돌

이 노드를 반환