# Algorithm 演算法 - 判圈系列 Brent 判圈算法(傳送龜算法)

# 簡介 Intro

![image.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1654668082663/zz7-fdNZq.png align="left")

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

## 解釋

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

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

### 進階題目

#### 找出迴圈長度

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

```python
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 喔（笑

```python

    # 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](https://www.geeksforgeeks.org/brents-cycle-detection-algorithm/)
- [Brent's Cycle Detection Algorithm (The Teleporting Turtle)](https://web.archive.org/web/20160304043822/http://www.siafoo.net/algorithm/11)