તમે Floyd's કાછુ અને સસલાનો ઉપયોગ કરીને ચક્રને કેવી રીતે શોધી શકો છો?

Question

IT Interview Practice · Accepted Answer

**Floyd's ચક્ર શોધ** એક અનુક્રમમાં (જેમ કે લિંક્ડ સૂચી) લૂપ શોધે છે જે બે પોઇન્ટરનો ઉપયોગ કરીને અલગ અલગ ગતિએ ફરે છે. જો ચક્ર અસ્તિત્વમાં હોય, તો ઝડપી પોઇન્ટર આખરે ધીમાને પછાડે અને મળે છે. તે **O(1)** વધારાની જગ્યા વાપરે છે.

## વિચાર

**slow** પોઇન્ટરને એક પગલું અને **fast** પોઇન્ટરને બે પગલાં આગળ بب કરો. ચક્રમાં, અંતર પ્રત્યેક પગલે એક ઘટે છે, તેથી તેઓ જોરથી અથડાવશે; ચક્ર વિના, 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's સતત જગ્યા વાપરે છે.

## ક્યારે વાપર કરવું / મુશ્કેલીઓ

**લિંક્ડ-સૂચી લૂપ શોધ**, ચક્રનું શરૂઆત શોધવું, અને કાર્યાત્મક આલેખમાં ચક્ર શોધવા માટે વાપર કરો (દરેક નોડના પાસે એક અનુગામી છે). હંમેશા `fast.next` ની રક્ષા કરો null દર્શન ટાળવા માટે. સામાન્ય આલેખ માટે, તેના બદલે DFS અને પુનરાવર્તન સ્ટેક વાપર કરો.

## શા માટે તે મહત્ત્વપૂર્ણ છે

ચક્ર શોધ સુરક્ષિત ટ્રાવર્સલ માટે આવશ્યક છે — એક અશોધાયેલ લૂપ અનંત પુનરાવર્તન મતલબ છે.

Floyd અલગોરિધમ એક ઓ(n)-જગ્યા સમસ્યા ઓ(1) જગ્યામાં એક ચતુર અપરિવર્તનીય સાથે હલ કરવાનું સુંદર ઉદાહરણ છે.

તે લિંક્ડ-સૂચી साક્ષાત્કાર અને રાજ્ય મશીનો અને સંખ્યા ક્રમમાં અનંત લૂપ શોધવામાં દેખાય છે.

વિચાર

ઉદાહરણ

જટિલતા

ક્યારે વાપર કરવું / મુશ્કેલીઓ

શા માટે તે મહત્ત્વપૂર્ણ છે

સંબંધિત પ્રશ્નો