Floyd యొక్క సైకిల్ గుర్తింపు ఒక క్రమాలో (linked list వంటి) రెండు పాయింటర్లను వేర్వేరు వేగంతో కదిలించడం ద్వారా లూప్ను కనుగొనండి. సైకిల్ ఉంటే, వేగవంత పాయింటర్ చివరకు నెమ్మదిగా ఉన్న పాయింటర్ను పట్టుకుని కలుసుకుంటుంది. ఇది O(1) అতిరేక స్థలాన్ని ఉపయోగిస్తుంది.
slow పాయింటర్ను ఒక దశ ద్వారా మరియు fast పాయింటర్ను రెండు దశల ద్వారా కదిలించండి. సైకిల్లో, ఖాళీ ప్రతి దశలో ఒకటిగా తగ్గుతుంది, కాబట్టి అవి తప్పనిసరిగా ఢీకొట్టాలి; సైకిల్ లేకుండా, వేగవంతం ముగింపుకు చేరుకుంటుంది.
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
Hash-set విధానం కూడా పనిచేస్తుంది కానీ O(n) స్థలం ఖర్చవుతుంది; Floyd యొక్క స్థిర స్థలాన్ని ఉపయోగిస్తుంది.
linked-list లూప్ గుర్తింపు, సైకిల్ ప్రారంభాన్ని కనుగొనడం, మరియు ఫంక్షనల్ గ్రాఫ్లలో సైకిల్లను గుర్తించడం (ప్రతి నోడ్ ఒక సక్సీడర్ ఉంది) కోసం ఉపయోగించండి. null dereferences నుండి తప్పించుకోవడానికి ఎల్లప్పుడూ fast.next రక్షించండి. సాధారణ గ్రాఫ్ల కోసం, బదులుగా recursion స్ట్యాక్తో DFS ఉపయోగించండి.
సైకిల్ గుర్తింపు సురక్షితమైన traversal కోసం ఎంపిక చేయబడింది — గుర్తించని లూప్ అనంత పునరావృత్తిని అర్థం చేస్తుంది.
Floyd యొక్క అల్గోరిథం ఒక O(n)-స్పేస్ సమస్యను O(1) స్పేస్లో తెలివైన అస్థిరంగా పరిష్కరించడానికి ఒక సుందరమైన ఉదాహరణ.
ఇది linked-list ఇంటర్వ్యూలలో మరియు state machines మరియు number sequences లో అనంతమైన లూప్లను గుర్తించడంలో కనిపిస్తుంది.