연결리스트 사이클 길이
-
[알고리즘/토끼와 거북이] 플로이드의 토끼와 거북이 (Floyd's Tortoise and Hare) 알고리즘Mhwan's Study/Algorithms 2021. 4. 16. 00:32
이번 포스팅은 플로이드의 토끼와 거북이 알고리즘입니다. 이 알고리즘은 Linked List에서 사이클이 있는지 확인, 사이클의 시작점, 사이클의 길이를 O(N) 시간복잡도 (공간복잡도는 O(1))로 알아낼 수 있습니다. 개인적으로 색다른 알고리즘이기도, 다양한 알고리즘 문제에서 활용하고 있는 알고리즘으로, 확실히 공부하고 싶은 마음에 올립니다. 위와 같은 사이클이 있는 연결리스트가 있다면 사이클의 시작점은 2, 사이클의 길이는 4입니다. 이를 알아내는 방법은 아래와 같습니다. # 사이클이 있는지 판단 1. 연결리스트의 시작점에 2개의 포인터를 놓습니다. (하나의 포인터는 토끼, 하나는 거북이라 부르겠습니다.) 2. 토끼라는 포인터는 한번 이동할때 2칸씩, 거북이는 한번에 한칸씩 이동합니다. 3. 이를 반..