Floyd'un kaplumbağası ve tavşanı kullanarak bir döngüyü nasıl tespit edersiniz?

Question

Accepted Answer

**Floyd'un döngü tespiti** bir dizideki (bağlı liste gibi) iki işaretçiyi farklı hızlarda hareket ettirerek bir döngü bulur. Bir döngü varsa, hızlı işaretçi sonunda yavaş işaretçiye yetişir ve onunla buluşur. **O(1)** ek alan kullanır.

## Fikir

**slow** işaretçiyi bir adım ve **fast** işaretçiyi iki adım hareket ettirin. Bir döngüde, boşluk her adımda bire düşer, bu yüzden çarpışmalı; döngü olmaksızın, hızlı işaretçi sona ulaşır.

## Örnek

```python
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next            # +1 step
        fast = fast.next.next       # +2 steps
        if slow is fast:            # pointers met -> cycle
            return True
    return False                    # fast hit the end -> no cycle
```

## Karmaşıklık

- **Zaman:** O(n). **Alan:** O(1).

Has-set yaklaşımı da işe yarasa da O(n) alan maliyeti; Floyd'un kullanabileceği sabit alan.

## Ne zaman kullanılır / Tehlikeler

**bağlı liste döngü tespiti**, döngünün başlangıcını bulma ve işlevsel grafiklerde döngüleri tespit etme (her düğümün bir ardılı vardır) için kullanın. null başvurusu hatasını önlemek için her zaman `fast.next` koruması yapın. Genel grafikler için bunun yerine özyineleme yığını ile DFS kullanın.

## Neden önemli

Döngü tespiti güvenli dolaşma için gereklidir — tespit edilmeyen bir döngü sonsuz yineleme anlamına gelir.

Floyd'un algoritması, bir O(n) uzay sorununun zekice bir değişmez ile O(1) uzayda çözülmesinin güzel bir örneğidir.

Bağlı liste görüşmelerinde ve durum makinelerinde ve sayı dizilerinde sonsuz döngülerin tespitinde görülür.