Πώς ανιχνεύετε έναν κύκλο χρησιμοποιώντας τη χελώνα και τον λαγό του Floyd;

Question

Accepted Answer

**Η ανίχνευση κύκλου του Floyd** βρίσκει ένα βρόχο σε μια ακολουθία (όπως μια linked list) χρησιμοποιώντας δύο δείκτες που κινούνται με διαφορετικές ταχύτητες. Εάν υπάρχει ένας κύκλος, ο γρήγορος δείκτης τελικά φτάνει και συναντά τον αργό δείκτη. Χρησιμοποιεί **O(1)** επιπλέον χώρο.

## Η ιδέα

Μετακινήστε έναν **slow** δείκτη ένα βήμα και έναν **fast** δείκτη δύο βήματα. Σε ένα κύκλο, το κενό μειώνεται κατά ένα σε κάθε βήμα, έτσι πρέπει να συγκρούονται· χωρίς κύκλο, ο γρήγορος δείκτης φτάνει στο τέλος.

## Παράδειγμα

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

## Πολυπλοκότητα

- **Χρόνος:** O(n). **Χώρος:** O(1).

Μια προσέγγιση με hash-set λειτουργεί επίσης αλλά κοστίζει O(n) χώρο· του Floyd χρησιμοποιεί σταθερό χώρο.

## Πότε να χρησιμοποιήσετε / Παγίδες

Χρησιμοποιήστε για **ανίχνευση βρόχου σε linked-list**, εύρεση της αρχής του κύκλου και ανίχνευση κύκλων σε συναρτησιακά γραφήματα (κάθε κόμβος έχει ένα διάδοχο). Πάντα προστατέψτε `fast.next` για να αποφύγετε null dereferences. Για γενικά γραφήματα, χρησιμοποιήστε DFS με ένα recursion stack αντ' αυτού.

## Γιατί είναι σημαντικό

Η ανίχνευση κύκλου είναι απαραίτητη για ασφαλή διέλευση — ένας μη ανιχνευμένος βρόχος σημαίνει άπειρη επανάληψη.

Ο αλγόριθμος του Floyd είναι ένα όμορφο παράδειγμα επίλυσης ενός προβλήματος O(n)-χώρου σε O(1) χώρο με ένα έξυπνο αμάραντο.

Εμφανίζεται σε συνεντεύξεις linked-list και στην ανίχνευση άπειρων βρόχων σε μηχανές κατάστασης και ακολουθίες αριθμών.