https://www.youtube.com/watch?v=pKO9UjSeLew&ab_channel=JomaTech

증명

Xi = 토끼와 거북이가 만난 지점  
i = 토끼와 거북이가 만나기 까지 거북이가 이동한거리  
Xμ = 사이클 시작지점  
μ = 리스트 시작지점부터 사이클 시작점까지 거리  
λ = 사이클의 순환길이  
m = 거북이가 사이클을 돈 횟수  
n = 토끼가 사이클을 돈 횟수  
y = xi에서 xμ사이의 거리  
거북이의 이동거리  
  i = μ + (m * λ) + y    -- 1  
거북이의 두배로 이동하는 토끼의 이동거리  
  2i = μ + (n * λ) + y    -- 2  
1과 2의 연립방정식  
  i = (n - m) * λ    -- 3  
사이클내 임의의 점 xj ( j >= μ )는 사이클의 임의(k)만큼 회전해도 같은점  
  Xj = X(j + k * λ)  
j = μ, k = (n - m) 대입  
  Xμ = X(μ + (n - m) * λ)  
  Xμ = X(μ + (n - m) * λ)  
3번 식에서 (n - m) * λ = i 이기에  
  xμ = x(μ + i)  
  
따라서 μ와 xi에서 μ의 거리가 같다는것을 증명  

Sudo

def floyd(f, x0):
    # Main phase of algorithm: finding a repetition x_i = x_2i.
    # The hare moves twice as quickly as the tortoise and
    # the distance between them increases by 1 at each step.
    # Eventually they will both be inside the cycle and then,
    # at some point, the distance between them will be
    # divisible by the period λ.
    tortoise = f(x0) # f(x0) is the element/node next to x0.
    hare = f(f(x0))
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(f(hare))
  
    # At this point the tortoise position, ν, which is also equal
    # to the distance between hare and tortoise, is divisible by
    # the period λ. So hare moving in circle one step at a time, 
    # and tortoise (reset to x0) moving towards the circle, will 
    # intersect at the beginning of the circle. Because the 
    # distance between them is constant at 2ν, a multiple of λ,
    # they will agree as soon as the tortoise reaches index μ.

    # Find the position μ of first repetition.    
    mu = 0
    tortoise = x0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)   # Hare and tortoise move at same speed
        mu += 1
 
    # Find the length of the shortest cycle starting from x_μ
    # The hare moves one step at a time while tortoise is still.
    # lam is incremented until λ is found.
    lam = 1
    hare = f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        lam += 1
 
    return lam, mu

이 코드는 포인터, 함수 평가 및 동등성 테스트를 저장하고 복사하는 방식으로만 시퀀스에 액세스합니다. 따라서 포인터 알고리즘으로 적합합니다. 알고리즘은  이러한 유형의 O ( λ  +  μ ) 작업과  O (1) 저장 공간을 사용합니다.