Si e zbuloni një cikël duke përdorur metodën e breshkës dhe lepur të Floydit?

Question

Accepted Answer

**Zbulimi i ciklit të Floydit** gjen një lak në një sekuencë (si një listë e lidhur) duke përdorur dy tregues që lëvizin me shpejtësi të ndryshme. Nëse ekziston një cikël, treguesi i shpejtë përfundimisht arrin dhe takohet me atë të ngadaltë. Përdor **O(1)** hapësirë shtesë.

## Ideja

Lëviz një tregues **slow** me një hap dhe një tregues **fast** me dy hapa. Në një cikël, hendeja zvogëlohet me një në secilin hap, prandaj duhet të përplasen; pa një cikël, treguesi i shpejtë arrin në fund.

## Shembull

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

## Kompleksiteti

- **Koha:** O(n). **Hapësira:** O(1).

Një qasje me hash-set funksionon gjithashtu, por kushton O(n) hapësirë; Floydit përdor hapësirë konstante.

## Kur duhet përdorur / kurthe

Përdorni për **zbulimin e ciklit në listën e lidhur**, gjetjen e fillimit të ciklit dhe zbulimin e cikleve në grafe funksionale (çdo nyje ka një pasues). Gjithmonë mbrojeni `fast.next` për të shmangur referenca null. Për grafikë të përgjithshëm, përdorni DFS me një stack rekurzion në vend.

## Pse është i rëndësishëm

Zbulimi i cikleve është thelbësor për përshkimin e sigurt — një lak i zbuluar do të thotë iterim pafund.

Algoritmi i Floydit është një shembull i bukur i zgjidhjes së një problemi O(n)-hapësire në hapësirën O(1) me një invariant të zgjuar.

Shfaqet në intervista të listave të lidhura dhe në zbulimin e cikleve të pafundme në makina me gjendje dhe sekuenca numerike.