Floyd's Algorithm 적용을 통한 Space Complexity O(N)에서 O(1)로 최적화

Context

Linked List 내 Cycle 시작 지점을 찾는 과정에서 HashSet을 이용한 단순 참조 저장 방식 사용. 모든 노드를 Set에 저장함에 따라 데이터 규모에 비례하여 메모리 사용량이 증가하는 O(N) Space Complexity의 한계 직면.

Technical Solution

• Slow(1 step)와 Fast(2 steps) 포인터를 활용한 Floyd's Cycle Detection Algorithm 도입
• 두 포인터의 속도 차이를 이용해 Cycle 내부에서 반드시 만나는 Meeting Point 생성
• Head부터 Cycle 시작점까지의 거리(L)와 Meeting Point에서 시작점까지의 거리가 수학적으로 동일함을 이용한 로직 설계
• Meeting Point 도달 후 한 포인터를 Head로 재설정하고 두 포인터를 동일 속도로 이동시켜 Cycle Entry Node를 식별
• 원본 리스트를 수정하지 않는 제약 사항을 준수하며 포인터 연산만으로 위치 추적