Floyd의주기 찾기 알고리즘에서 두 개 이상의 노드 건너 뛰기 알고리즘

Question

오늘은 연결된 목록에서 루프를 감지하는 Floyd의 알고리즘을 읽었습니다. 더 빠른 루프 감지를 위해 하나 이상의 노드 (예 : 2) 을 건너 뛰면 더 좋지 않을까 궁금합니다. 예를 들어

: fastptr을 변화시키면서 부작용이 고려 될 것이다

fastptr=fastptr->next->next->next. 

참고.

Answer 1

제안 사항은 정확하지만 알고리즘 속도는 변경되지 않습니다. 당신이 wiki에서 거북이와 토끼 알고리즘을 살펴 걸릴 경우

알고리즘의 핵심 통찰력은, 어떤 정수에 대해 내가 ≥ μ와 ≥ 0 K, 있다는 것입니다을 X _내가 = X _{내가 + kλ}, λ는 루프의 길이이고 μ는 루프의 시작 위치입니다. 특히 난 = kλ ≥ μ는 팔로우마다 X _제가 = X _2I있다.

굵은 부분에서

, 당신은 또한 X _내가 = X _3I에게 또는 다른 계수를, 말할 수 있지만, 키 통찰력이 내가을 찾는 것입니다, 당신을 점프 얼마나 많은과 중요하지 않아 알고리즘의 순서는 알고리즘 의 위치에 따라 다릅니다.