Kif tutkunu ċiklu bit-tortuga u l-erpum ta' Floyd?

Question

Accepted Answer

**Floyd's cycle detection** isib ħalqa f'sekwenza (bħal linked list) bl-użu ta' żewġ pointers li jiċċaqalqu b'veloċitajiet differenti. Jekk ċiklu jeżisti, il-pointer mabugħ eventwalment jiltaqa' ma' dak il-bnegħa. Juża **O(1)** spazju addizzjonali.

## L-idea

imbexx il-pointer **slow** pass wieħed u l-pointer **fast** pass żewġ. F'ċiklu, il-ġappja tonqos waħda kull pass, u għalhekk għandu jkollhom kkollizzjoni; mingħajr ċiklu, il-pointer mabugħ jilħaq l-aħħar.

## Eżempju

```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
```

## Kumplessità

- **Ħin:** O(n). **Spazju:** O(1).

L-approċċ hash-set jaħdem ukoll iżda jkellef O(n) spazju; Floyd's juża spazju kostanti.

## Waħda tuża / trappoli

Uża għal **deteċċjoni ta' ħalqa linked-list**, isib l-istat tal-ċiklu, u deteċċjoni ta' ċikli f'graffs funzjonali (kull node għandu suksessur wieħed). Tprottezzetta dejjem `fast.next` biex tevita null dereference. Għal graffs ġenerali, uża DFS b'stack ta' rikursjoni.

## Għaliex huwa importanti

Deteċċjoni ta' ċikli hija essenzjali għal traversal sigur — ħalqa li ma' ġietx misjuba tfisser iterazzjoni infinita.

L-algoritmu ta' Floyd huwa eżempju sabih ta' soluzzjoni ta' problema O(n)-spazju f'O(1) spazju b'invariant ċar.

Jidher f'entrevisti ta' linked-list u fl-idetezzjoni ta' ħalaq infinit f'magni tal-istati u sekwenzi ta' numri.