ਤੁਸੀਂ Floyd ਦੇ tortoise ਅਤੇ hare ਨਾਲ ਇੱਕ cycle ਨੂੰ ਕਿਵੇਂ detect ਕਰਦੇ ਹੋ?

Question

Accepted Answer

**Floyd's cycle detection** ਇੱਕ ਕ੍ਰਮ (ਜਿਵੇਂ linked list) ਵਿੱਚ ਇੱਕ loop ਨੂੰ ਦੋ pointers ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਲੱਭਦਾ ਹੈ ਜੋ ਵੱਖ-ਵੱਖ ਗਤੀ ਨਾਲ ਚਲਦੇ ਹਨ। ਜੇ ਇੱਕ cycle ਮੌਜੂਦ ਹੈ, ਤਾਂ ਤੇਜ਼ pointer ਆਖਰਕਾਰ slow ਨੂੰ lap ਕਰਦਾ ਹੈ ਅਤੇ ਇਸ ਨੂੰ ਮਿਲਦਾ ਹੈ। ਇਹ **O(1)** ਵਾਧੂ ਥਾਂ ਦੀ ਵਰਤੋਂ ਕਰਦਾ ਹੈ।

## ਧਾਰਨਾ

ਇੱਕ **slow** pointer ਨੂੰ ਇੱਕ ਕਦਮ ਅਤੇ ਇੱਕ **fast** pointer ਨੂੰ ਦੋ ਕਦਮ ਚਲਾਓ। ਇੱਕ cycle ਵਿੱਚ, ਵਿੱਚਕਾਰ ਦੀ ਦੂਰੀ ਹਰ ਕਦਮ ਨਾਲ ਇੱਕ ਘੱਟ ਹੋ ਜਾਂਦੀ ਹੈ, ਇਸ ਲਈ ਉਹ ਲਾਜ਼ਮੀ ਤੌਰ 'ਤੇ ਟਕਰਾਉਂਦੇ ਹਨ; cycle ਤੋਂ ਬਿਨਾ, 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
```

## Complexity

- **ਸਮਾਂ:** O(n)। **ਥਾਂ:** O(1)।

ਇੱਕ hash-set ਪਹੁੰਚ ਵੀ ਕੰਮ ਕਰਦੀ ਹੈ ਪਰ O(n) ਥਾਂ ਦੀ ਕੀਮਤ ਦਿੰਦੀ ਹੈ; Floyd's constant ਥਾਂ ਦੀ ਵਰਤੋਂ ਕਰਦਾ ਹੈ।

## ਕਦੋਂ ਵਰਤੋਂ / pitfalls

**linked-list loop detection**, cycle ਦੀ ਸ਼ੁਰੁਆਤ ਲੱਭਣਾ, ਅਤੇ functional graphs ਵਿੱਚ cycles ਨੂੰ detect ਕਰਨ ਲਈ ਵਰਤੋਂ (ਹਰ node ਦੇ ਕੋਲ ਇੱਕ successor ਹੈ)। ਹਮੇਸ਼ਾ `fast.next` ਨੂੰ null dereferences ਤੋਂ ਬਚਾਉਣ ਲਈ guard ਕਰੋ। ਆਮ graphs ਲਈ, ਇਸਦੀ ਬਜਾਏ recursion stack ਦੇ ਨਾਲ DFS ਵਰਤੋ।

## ਇਹ ਕਿਉਂ ਮਾਇਨੇ ਰੱਖਦਾ ਹੈ

Cycles ਦਾ ਪਤਾ ਲਗਾਉਣਾ ਸੁਰੱਖਿਤ traversal ਲਈ ਜ਼ਰੂਰੀ ਹੈ — ਇੱਕ ਖੋਜਤ ਨਾ ਕੀਤਾ loop ਦਾ ਮਤਲਬ infinite iteration ਹੈ।

Floyd's algorithm ਇੱਕ ਖੂਬਸੂਰਤ ਉਦਾਹਰਨ ਹੈ ਜਿਥੇ ਇੱਕ O(n)-space ਸਮੱਸਿਆ ਨੂੰ ਇੱਕ ਹੋਸ਼ਿਆਰ invariant ਨਾਲ O(1) ਥਾਂ ਵਿੱਚ ਹੱਲ ਕੀਤਾ ਜਾਂਦਾ ਹੈ।

ਇਹ linked-list interviews ਵਿੱਚ ਅਤੇ state machines ਅਤੇ number sequences ਵਿੱਚ infinite loops ਦਾ ਪਤਾ ਲਗਾਉਣ ਵਿੱਚ ਦਿਖਾਈ ਦਿੰਦਾ ਹੈ।