簡介 Intro

根據演算法期會比 Floyd 的方式快 24-36% 的速度。

解釋

這個演算法的方式其實基本上跟 Floyd 不一樣的地方在於龜兔的移動方式。在 Floyd 的演算法中，龜兔會一起移動，只是步數的不同。但在 Brent 的演算法中，只有兔子在移動。

每次兔子移動後，烏龜會馬上傳送到跟兔子一樣的位置（所以才叫 Teleporint Turtle）。然後兔子在將步數倍增移動。例如兔子第一次移動 1 格、再來 2 格、4 格一直走到底或是遇到烏龜。

進階題目

找出迴圈長度

當相遇時，兔子從原本位置走到烏龜的位置就是迴圈的長度。為什麼呢？因為當兔子要開始走的時候，假設位置是 x，烏龜會需要先瞬移到兔子現在的位置 x。而兔子從 x 走到烏龜的位置，不就是整整繞了一圈嗎？因此當下兔子走的步數就是迴圈的長度

def detectCycle(self):
    # if head is null
    # then no loop
    temp = self.head

    if not (temp):
        return False
    tortoise = temp
    hare = temp.next
    power = 1
    length = 1

    # This loop runs till we
    # find the loop. If there
    # is no loop then second
    # pointer ends at NULL
    while hare and hare != tortoise:

        # condition after which
        # we will update the power
        # and length as smallest
        # power of two gives
        # the start of cycle.
        if length == power:

            # updating the power.
            power *= 2

            # updating the length
            length = 0

            tortoise = hare

        hare = hare.next
        length += 1
    # if it is null then no loop
    if not (hare):
        return

找出迴圈連結點

要找出連結點的話，在找出迴圈長度後。只要將兔子放回開頭，而烏龜放到從起點走回圈長度的距離（就是 length + 1）。之後兩個同時一步一步走，走到相遇就是起點了。

這邊要來講說為什麼，發現網路上都只跟我說這樣就好，但原理還是要理解才不容易忘。

假設迴圈長度 C、起點到迴圈連接點的長度是 L。然後從連接點到烏龜的點是 A，烏龜的位置到連接點長度是 B。

A + B = C
A = C - L
C - L + B = C
C - C + B = L
B = L

所以就是 BL 喔（笑

    # Now set tortoise pointer
    # to the beginning and
    # hare pointer to
    # beginning plus cycle
    # length which is length.
    tortoise = hare = self.head
    while length > 0:
        hare = hare.next
        length = length - 1

    # Now move both pointers
    # at same speed so that
    # they meet at the
    # beginning of loop.
    while hare != tortoise:
        hare = hare.next
        tortoise = tortoise.next

    return tortoise

Reference

• Brent’s Cycle Detection Algorithm
• Brent's Cycle Detection Algorithm (The Teleporting Turtle)