Floyd 주기는 주어진 단일 연결 목록에서 주기를 감지하는 주기 감지 알고리즘 중 하나입니다.
Floyd Cycle 알고리즘에는 처음에 머리를 가리키는 두 개의 포인터가 있습니다. 토끼와 거북이 이야기에서 토끼는 거북이보다 2배 빠르게 움직이며 토끼가 길의 끝에 도달할 때마다 거북이는 길의 중간에 도달합니다.
알고리즘
-
List의 헤드 노드에서 Hare와 Tortoise를 초기화합니다.
-
처음에는 토끼가 거북이보다 두 배 빠르게 움직입니다.
-
토끼와 거북이 둘 다 움직여서 토끼가 연결 목록의 끝에 도달했는지 확인하고 목록에 루프가 없으므로 반환합니다.
-
그렇지 않으면 토끼와 거북이가 모두 앞으로 나아갑니다.
-
Hare와 Tortoise가 같은 노드에 있으면 목록 주기를 찾았으므로 반환합니다.
-
그렇지 않으면 2단계부터 시작하세요.
위 알고리즘에 대한 의사 코드
tortoise := headNode hare := headNode foreach: if hare == end return 'There is No Loop Found.' hare := hare.next if hare == end return 'No Loop Found' hare = hare.next tortoise = tortoise.next if hare == tortoise return 'Cycle Detected'