쿼카러버의 기술 블로그

문제 Leetcode의 141번 문제를 보면 Tortoise and hare, 즉 토끼와 거북이 알고리즘으로 유명한 문제가 있다. 문제는 간단하게 말하자면 링크드리스트가 주어지고, 해당 링크드리스크가 싸이클이 있는지 없는지를 확인하는 문제가 주어진다. 입력 : 링크드 리스트의 head 출력 : 사이클이 있으면 true 없으면 false를 리턴 예를 들면 아래와 같이 사이클이 있는 링크드 리스트와 사이클이 없는 링크드 리스트가 있을텐데, 이 중에서 싸이클이 있는 케이스를 판별한다는 것이다. 사이클이 없는 링크드 리스트 사이클이 있는 링크드 리스트 위 알고리즘은 해쉬맵을 사용해서도 풀 수 있지만 가장 정석 방법은 Floyd가 제안한 cycle detection 알고리즘이다. 본 문제는 해당 알고리즘을 사용해..