లూప్ ఉన్న లింక్ చేయబడిన జాబితా యొక్క ముగింపు నోడ్ NULL కాకుండా అదే జాబితాలోని మరొక నోడ్‌ను సూచిస్తుంది. లింక్ చేయబడిన జాబితాలో తదుపరి పాయింటర్‌ని అనుసరించడం ద్వారా పదేపదే యాక్సెస్ చేయగల నోడ్ ఉంటే, జాబితా ఇలా చెప్పబడుతుంది. ఒక చక్రం కలిగి.
సాధారణంగా, లింక్డ్ జాబితా యొక్క చివరి నోడ్ జాబితా ముగింపును సూచించడానికి NULL సూచనను సూచిస్తుంది. అయినప్పటికీ, లూప్‌తో లింక్ చేయబడిన జాబితాలో, జాబితా యొక్క ముగింపు నోడ్ ప్రారంభ నోడ్, అంతర్గత నోడ్ లేదా దానికదే సూచిస్తుంది. కాబట్టి, అటువంటి పరిస్థితులలో, మేము తదుపరి నోడ్ యొక్క సూచనను NULLకి సెట్ చేయడం ద్వారా లూప్‌ను గుర్తించి, ముగించాలి. లింక్ చేయబడిన జాబితాలోని లూప్ యొక్క గుర్తింపు భాగం ఈ కథనంలో వివరించబడింది.
C++లో, లింక్ చేయబడిన జాబితాలో లూప్‌లను కనుగొనడానికి అనేక మార్గాలు ఉన్నాయి:
హాష్ టేబుల్ ఆధారిత విధానం : ఈ విధానం సందర్శించిన నోడ్‌ల చిరునామాలను హాష్ పట్టికలో నిల్వ చేస్తుంది. హ్యాష్ పట్టికలో నోడ్ ఇప్పటికే ఉన్నట్లయితే, దాన్ని మళ్లీ సందర్శించినప్పుడు లింక్ చేయబడిన జాబితాలో లూప్ ఉంటుంది.
ఫ్లాయిడ్ సైకిల్ విధానం : 'తాబేలు మరియు కుందేలు' అల్గోరిథం, సాధారణంగా ఫ్లాయిడ్ యొక్క సైకిల్-ఫైండింగ్ అల్గారిథమ్ అని పిలుస్తారు: ఈ సాంకేతికత రెండు పాయింటర్లను ఉపయోగించుకుంటుంది, ఒకటి మరొకదాని కంటే నెమ్మదిగా కదులుతుంది మరియు మరొకటి వేగంగా కదులుతుంది. లూప్ ఉనికిని వెల్లడిస్తూ, లింక్ చేయబడిన జాబితాలో లూప్ ఉన్నట్లయితే త్వరిత పాయింటర్ చివరికి స్లోయర్ పాయింటర్‌ను అధిగమిస్తుంది.
పునరావృత పద్ధతి : ఈ పద్ధతి మళ్లీ మళ్లీ కాల్ చేయడం ద్వారా లింక్ చేయబడిన జాబితా ద్వారా వెళుతుంది. ప్రస్తుత నోడ్ మునుపు సందర్శించినట్లయితే లింక్ చేయబడిన జాబితాలో లూప్ ఉంటుంది.
స్టాక్ ఆధారిత విధానం : ఈ విధానం సందర్శించిన నోడ్‌ల చిరునామాలను స్టాక్‌లో నిల్వ చేస్తుంది. మళ్లీ సందర్శించినప్పుడు స్టాక్‌లో నోడ్ ఇప్పటికే ఉన్నట్లయితే లింక్ చేయబడిన జాబితాలో లూప్ ఉంటుంది.
భావనను అర్థం చేసుకోవడానికి ప్రతి విధానాన్ని వివరంగా వివరించండి.
విధానం 1: HashSet అప్రోచ్
హ్యాషింగ్‌ని ఉపయోగించడం అనేది చాలా సరళమైన పద్ధతి. ఇక్కడ, నోడ్ చిరునామాలతో హాష్ పట్టికను ఉంచేటప్పుడు మేము జాబితాను ఒక్కొక్కటిగా పరిశీలిస్తాము. అందువల్ల, హాష్ పట్టికలో ఇప్పటికే ఉన్న ప్రస్తుత నోడ్ యొక్క తదుపరి చిరునామాను మనం ఎప్పుడైనా అమలు చేస్తే లూప్ ఉనికిలో ఉంటుంది. అలా కాకుండా, మనం NULL (అంటే, లింక్డ్ లిస్ట్ ముగింపుకు చేరుకుంటే) లింక్డ్ లిస్ట్‌లో లూప్ ఉండదు.
ఈ వ్యూహాన్ని అమలు చేయడం చాలా సులభం.
లింక్ చేయబడిన జాబితాను దాటుతున్నప్పుడు, మేము unordered_hashmapని ఉపయోగిస్తాము మరియు దానికి నోడ్‌లను జోడిస్తూనే ఉంటాము.
ఇప్పుడు, మ్యాప్‌లో ఇప్పటికే చూపబడిన నోడ్‌ని చూసిన తర్వాత, మనం లూప్ ప్రారంభానికి చేరుకున్నామని మనకు తెలుస్తుంది.
-
- అదనంగా, మేము ప్రతి దశలో రెండు పాయింటర్లను ఉంచాము, తల నోడ్ ప్రస్తుత నోడ్‌కు గురిపెట్టి మరియు చివరి నోడ్ పునరావృతం చేస్తున్నప్పుడు, ప్రస్తుత నోడ్ యొక్క పూర్వ నోడ్‌ను సూచిస్తోంది.
- మా వంటి తల నోడ్ ఇప్పుడు లూప్ యొక్క ప్రారంభ నోడ్‌ని చూపుతోంది చివరి నోడ్ తల చూపుతున్న నోడ్‌ను చూపుతోంది (అనగా, ఇది సూచిస్తుంది చివరి నోడ్ లూప్), మా తల నోడ్ ప్రస్తుతం లూప్ యొక్క ప్రారంభ నోడ్‌ను సూచిస్తోంది.
- l సెట్ చేయడం ద్వారా లూప్ విచ్ఛిన్నమవుతుంది astNode->తదుపరి == NULL .
ఇలా చేయడం ద్వారా, లూప్ యొక్క ప్రారంభ నోడ్‌ని సూచించడానికి బదులుగా ముగింపు లూప్ నోడ్, NULLకి సూచించడం ప్రారంభమవుతుంది.
హాషింగ్ పద్ధతి యొక్క సగటు సమయం మరియు స్థలం సంక్లిష్టత O(n). ప్రోగ్రామింగ్ లాంగ్వేజ్‌లో అంతర్నిర్మిత హాషింగ్ డేటాస్ట్రక్చర్ అమలు చేయడం వల్ల హ్యాషింగ్‌లో ఢీకొన్న సందర్భంలో మొత్తం సమయ సంక్లిష్టతను నిర్ణయిస్తుందని రీడర్ ఎల్లప్పుడూ తెలుసుకోవాలి.
పై పద్ధతి కోసం C++ ప్రోగ్రామ్ అమలు (HashSet):
#
నేమ్‌స్పేస్ stdని ఉపయోగించడం;
struct నోడ్ {
పూర్ణాంక విలువ;
struct నోడ్ * తరువాత;
} ;
నోడ్ * కొత్త నోడ్ ( పూర్ణాంక విలువ )
{
నోడ్ * టెంప్నోడ్ = కొత్త నోడ్;
టెంప్నోడ్- > విలువ = విలువ;
టెంప్నోడ్- > తదుపరి = NULL;
తిరిగి టెంప్నోడ్;
}
// ఏదైనా సంభావ్య లూప్‌లను గుర్తించండి మరియు తొలగించండి
// లో ఈ ఫంక్షన్‌తో లింక్ చేయబడిన జాబితా.
శూన్యం ఫంక్షన్HashMap ( నోడ్ * తల నోడ్ )
{
// Hash మ్యాప్‌ని అమలు చేయడానికి unordered_map సృష్టించబడింది
unordered_map < నోడ్ * , Int > హాష్_మ్యాప్;
// లాస్ట్‌నోడ్‌కి పాయింటర్
నోడ్ * చివరి నోడ్ = NULL;
అయితే ( తల నోడ్ ! = శూన్యం ) {
// మ్యాప్ నుండి నోడ్ లేకుంటే, దాన్ని జోడించండి.
ఉంటే ( hash_map.find ( తల నోడ్ ) == hash_map.end ( ) ) {
హాష్_మ్యాప్ [ తల నోడ్ ] ++;
చివరి నోడ్ = తల నోడ్;
హెడ్‌నోడ్ = హెడ్‌నోడ్- > తరువాత;
}
// ఒక చక్రం ఉన్నట్లయితే, సెట్ చివరి నోడ్ NULLకి తదుపరి పాయింటర్.
లేకపోతే {
lastNode-> తదుపరి = NULL;
బ్రేక్;
}
}
}
// లింక్ చేయబడిన జాబితాను ప్రదర్శించు
శూన్య ప్రదర్శన (నోడ్* హెడ్‌నోడ్)
{
అయితే (హెడ్‌నోడ్ != NULL) {
కౌట్ << headNode->విలువ << ' ';
headNode = తల నోడ్-> తదుపరి;
}
కౌట్ << endl;
}
/* ప్రధాన విధి*/
int ప్రధాన()
{
నోడ్* హెడ్‌నోడ్ = కొత్త నోడ్(48);
headNode-> next = headNode;
హెడ్‌నోడ్-> తదుపరి = కొత్త నోడ్(18);
headNode-> next-> next = newNode(13);
headNode-> next-> next-> next = newNode(2);
headNode->తదుపరి->తదుపరి->తదుపరి->తదుపరి = కొత్తనోడ్(8);
/* లింక్డ్‌లిస్ట్‌లో లూప్‌ను సృష్టించండి */
headNode->next->next->next->next->next = headNode->next-> next;
ఫంక్షన్‌హాష్‌మ్యాప్ (హెడ్‌నోడ్);
printf('లూప్ లేకుండా లింక్ చేయబడిన జాబితా \n');
ప్రదర్శన (హెడ్‌నోడ్);
తిరిగి 0;
}
అవుట్‌పుట్:
లూప్ లేకుండా లింక్ చేయబడిన జాబితా
48 18 13 2 8
కోడ్ యొక్క దశల వారీ వివరణ క్రింద అందించబడింది:
-
- అన్ని సాధారణ C++ లైబ్రరీలను కలిగి ఉన్న bits/stdc++.h> హెడర్ ఫైల్ కోడ్‌లో చేర్చబడింది.
- 'నోడ్' అనే నిర్మాణం నిర్మించబడింది మరియు దీనికి ఇద్దరు సభ్యులు ఉన్నారు: జాబితాలోని తదుపరి నోడ్‌కు సూచన మరియు 'విలువ' అని పిలువబడే పూర్ణాంకం.
- పూర్ణాంక విలువను దాని ఇన్‌పుట్‌గా మరియు “తదుపరి” పాయింటర్‌తో NULLకి సెట్ చేస్తే, “newNode” ఫంక్షన్ ఆ విలువతో కొత్త నోడ్‌ను సృష్టిస్తుంది.
- ఫంక్షన్' ఫంక్షన్ హాష్ మ్యాప్' నిర్వచించబడింది, ఇది ఇన్‌పుట్‌గా లింక్ చేయబడిన జాబితా యొక్క హెడ్ నోడ్‌కు పాయింటర్‌ను తీసుకుంటుంది.
- లోపల ' ఫంక్షన్ హాష్ మ్యాప్ ' ఫంక్షన్, 'hash_map' పేరుతో ఒక unordered_map సృష్టించబడింది, ఇది హాష్ మ్యాప్ డేటా నిర్మాణాన్ని అమలు చేయడానికి ఉపయోగించబడుతుంది.
- జాబితా యొక్క చివరి నోడ్‌కు పాయింటర్ NULLకి ప్రారంభించబడింది.
- లింక్ చేయబడిన జాబితాను దాటడానికి కాసేపు లూప్ ఉపయోగించబడుతుంది, ఇది హెడ్ నోడ్ నుండి మొదలై హెడ్ నోడ్ NULL అయ్యే వరకు కొనసాగుతుంది.
- హాష్ మ్యాప్‌లో ప్రస్తుత నోడ్ (హెడ్‌నోడ్) ఇప్పటికే లేనట్లయితే, లాస్ట్‌నోడ్ పాయింటర్ while లూప్‌లోని ప్రస్తుత నోడ్‌కి నవీకరించబడుతుంది.
- మ్యాప్‌లో ప్రస్తుత నోడ్ కనుగొనబడితే, లింక్ చేయబడిన జాబితాలో లూప్ ఉందని అర్థం. లూప్‌ను తీసివేయడానికి, తదుపరి పాయింటర్ చివరి నోడ్ సెట్ చేయబడింది శూన్య మరియు అయితే లూప్ విచ్ఛిన్నమైంది.
- లింక్ చేయబడిన జాబితా యొక్క హెడ్ నోడ్ 'డిస్ప్లే' అనే ఫంక్షన్‌కు ఇన్‌పుట్‌గా ఉపయోగించబడుతుంది, ఇది జాబితాలోని ప్రతి నోడ్ విలువను మొదటి నుండి ముగింపు వరకు అవుట్‌పుట్ చేస్తుంది.
- లో ప్రధాన ఫంక్షన్, ఒక లూప్ సృష్టించడం.
- 'functionHashMap' ఫంక్షన్‌ను హెడ్‌నోడ్ పాయింటర్‌తో ఇన్‌పుట్‌గా పిలుస్తారు, ఇది జాబితా నుండి లూప్‌ను తీసివేస్తుంది.
- సవరించిన జాబితా 'డిస్ప్లే' ఫంక్షన్‌ని ఉపయోగించి ప్రదర్శించబడుతుంది.
విధానం 2: ఫ్లాయిడ్స్ సైకిల్
ఫ్లాయిడ్ యొక్క సైకిల్ డిటెక్షన్ అల్గారిథమ్, దీనిని తరచుగా తాబేలు మరియు కుందేలు అల్గారిథమ్ అని పిలుస్తారు, ఇది లింక్ చేయబడిన జాబితాలో సైకిల్‌లను గుర్తించే ఈ పద్ధతికి పునాదిని అందిస్తుంది. 'స్లో' పాయింటర్ మరియు 'ఫాస్ట్' పాయింటర్, ఇది వివిధ వేగంతో జాబితాను దాటుతుంది, ఈ టెక్నిక్‌లో ఉపయోగించే రెండు పాయింటర్‌లు. వేగవంతమైన పాయింటర్ రెండు దశలను ముందుకు తీసుకువెళుతుంది, అయితే స్లో పాయింటర్ ప్రతి పునరావృతానికి ఒక అడుగు ముందుకు వేస్తుంది. రెండు పాయింట్లు ఎప్పుడైనా ముఖాముఖిగా వచ్చినట్లయితే లింక్ చేయబడిన జాబితాలో ఒక చక్రం ఉంటుంది.
1. లింక్ చేయబడిన జాబితా యొక్క హెడ్ నోడ్‌తో, మేము ఫాస్ట్ మరియు స్లో అనే రెండు పాయింటర్లను ప్రారంభిస్తాము.
2. ఇప్పుడు మనం లింక్ చేయబడిన జాబితా ద్వారా తరలించడానికి లూప్‌ను అమలు చేస్తాము. వేగవంతమైన పాయింటర్‌ను ప్రతి పునరావృత దశ వద్ద స్లో పాయింటర్‌కు ముందు రెండు స్థానాలకు తరలించాలి.
3. ఫాస్ట్ పాయింటర్ జాబితా ముగింపుకు చేరుకుంటే లింక్ చేయబడిన జాబితాలో లూప్ ఉండదు (fastPointer == NULL లేదా fastPointer->next == NULL). కాకపోతే, వేగవంతమైన మరియు నెమ్మదిగా ఉండే పాయింటర్‌లు చివరికి కలుస్తాయి, అంటే లింక్ చేయబడిన జాబితాలో లూప్ ఉంటుంది.
పై పద్ధతికి C++ ప్రోగ్రామ్ అమలు (ఫ్లాయిడ్ సైకిల్):
#
నేమ్‌స్పేస్ stdని ఉపయోగించడం;
/* లింక్ జాబితా నోడ్ */
struct నోడ్ {
int డేటా;
struct నోడ్ * తరువాత;
} ;
/* లూప్‌ను తీసివేయడానికి ఫంక్షన్. */
శూన్యం deleteLoop ( struct నోడ్ * , స్ట్రక్ట్ నోడ్ * ) ;
/* ఈ ఫంక్షన్ జాబితా లూప్‌లను గుర్తించి తొలగిస్తుంది. ఇది దిగుబడిని ఇస్తుంది 1
ఉంటే ఒక లూప్ ఉంది లో జాబితా; లేకపోతే , అది తిరిగి వస్తుంది 0 . */
int detectAndDeleteLoop ( struct నోడ్ * జాబితా )
{
struct నోడ్ * slowPTR = జాబితా, * fastPTR = జాబితా;
// తనిఖీ చేయడానికి పునరావృతం చేయండి ఉంటే లూప్ ఉంది.
అయితే ( నెమ్మదిగాPTR && ఫాస్ట్PTR && ఫాస్ట్‌పిటిఆర్- > తరువాత ) {
slowPTR = slowPTR- > తరువాత;
fastPTR = fastPTR- > తరువాత- > తరువాత;
/* ఏదో ఒక సమయంలో స్లోపీటీఆర్ మరియు ఫాస్ట్‌పీటీఆర్ కలిసినట్లయితే అప్పుడు అక్కడ
ఒక లూప్ */
ఉంటే ( slowPTR == fastPTR ) {
deleteLoop ( నెమ్మదిగాPTR, జాబితా ) ;
/* తిరిగి 1 ఒక లూప్ కనుగొనబడిందని సూచించడానికి. */
తిరిగి 1 ;
}
}
/* తిరిగి 0 లూప్ కనుగొనబడలేదని సూచించడానికి. */
తిరిగి 0 ;
}
/* లింక్ చేయబడిన జాబితా నుండి లూప్‌ను తొలగించే ఫంక్షన్.
లూప్‌నోడ్ లూప్ నోడ్‌లలో ఒకదానికి గురిచేస్తోంది మరియు హెడ్‌నోడ్ గురిపెట్టింది
లింక్ చేయబడిన జాబితా యొక్క ప్రారంభ నోడ్‌కు */
శూన్యం deleteLoop ( struct నోడ్ * లూప్‌నోడ్, స్ట్రక్ట్ నోడ్ * తల నోడ్ )
{
struct నోడ్ * ptr1 = loopNode;
struct నోడ్ * ptr2 = loopNode;
// ఎన్ని నోడ్స్ ఉన్నాయో లెక్కించండి లో లూప్.
సంతకం చేయని int k = 1 , నేను;
అయితే ( ptr1- > తరువాత ! = ptr2 ) {
ptr1 = ptr1- > తరువాత;
k++;
}
// హెడ్‌నోడ్‌కి ఒక పాయింటర్‌ని పరిష్కరించండి
ptr1 = headNode;
// మరియు హెడ్‌నోడ్ తర్వాత k నోడ్‌లకు ఇతర పాయింటర్
ptr2 = headNode;
కోసం ( నేను = 0 ; i < k; i++ )
ptr2 = ptr2- > తరువాత;
/* రెండు పాయింట్లను ఏకకాలంలో తరలించినప్పుడు,
వారు లూప్ వద్ద ఢీకొంటారు యొక్క ప్రారంభ నోడ్. */
అయితే (ptr2 != ptr1) {
ptr1 = ptr1->తదుపరి;
ptr2 = ptr2->తదుపరి;
}
// నోడ్ పొందండి' లు చివరి పాయింటర్.
అయితే ( ptr2- > తరువాత ! = ptr1 )
ptr2 = ptr2- > తరువాత;
/* లూప్‌ను మూసివేయడానికి, సెట్ తదుపరి
లూప్‌కు నోడ్ యొక్క ముగింపు నోడ్. */
ptr2-> తదుపరి = NULL;
}
/* లింక్ చేయబడిన జాబితాను ప్రదర్శించడానికి ఫంక్షన్ */
శూన్యం డిస్ప్లే లింక్డ్‌లిస్ట్ (స్రక్ట్ నోడ్* నోడ్)
{
// లూప్‌ను తొలగించిన తర్వాత లింక్ చేసిన జాబితాను ప్రదర్శించండి
అయితే (నోడ్ != NULL) {
cout << node->డేటా << ' ';
నోడ్ = నోడ్-> తదుపరి;
}
}
స్ట్రక్ట్ నోడ్* కొత్తనోడ్ (పూర్ణాంక కీ)
{
స్ట్రక్ట్ నోడ్* టెంప్ = కొత్త నోడ్();
temp->data = కీ;
temp-> next = NULL;
తిరిగి ఉష్ణోగ్రత;
}
// ప్రధాన కోడ్
int ప్రధాన()
{
స్ట్రక్ట్ నోడ్* హెడ్‌నోడ్ = కొత్త నోడ్(48);
హెడ్‌నోడ్-> తదుపరి = కొత్త నోడ్(18);
headNode-> next-> next = newNode(13);
headNode-> next-> next-> next = newNode(2);
headNode->తదుపరి->తదుపరి->తదుపరి->తదుపరి = కొత్తనోడ్(8);
/* లూప్ సృష్టించండి */
headNode->next->next->next->next->next = headNode->next-> next;
// లింక్ చేయబడిన జాబితాలో లూప్‌ను ప్రదర్శించండి
//displayLinkedList(headNode);
డిటెక్ట్ అండ్ డిలీట్ లూప్ (హెడ్ నోడ్);
కౌట్ << 'లూప్ లేని తర్వాత లింక్ చేయబడిన జాబితా \n';
డిస్ప్లేలింక్డ్‌లిస్ట్ (హెడ్‌నోడ్);
తిరిగి 0;
}
అవుట్‌పుట్:
లూప్ లేని తర్వాత లింక్ చేయబడిన జాబితా
48 18 13 2 8
వివరణ:
-
- “bits/stdc++.h” మరియు “std::cout,” వంటి సంబంధిత హెడర్‌లు ముందుగా చేర్చబడ్డాయి.
- లింక్ చేయబడిన జాబితాలోని నోడ్‌ని సూచించే “నోడ్” స్ట్రక్ట్ అప్పుడు ప్రకటించబడుతుంది. జాబితాలోని క్రింది నోడ్‌కు దారితీసే తదుపరి పాయింటర్ ప్రతి నోడ్‌లోని పూర్ణాంక డేటా ఫీల్డ్‌తో పాటు చేర్చబడుతుంది.
- అప్పుడు, ఇది 'deleteLoop' మరియు 'detectAndDeleteLoop,' రెండు ఫంక్షన్లను నిర్వచిస్తుంది. మొదటి పద్ధతిని ఉపయోగించి లింక్ చేయబడిన జాబితా నుండి లూప్ తీసివేయబడుతుంది మరియు రెండవ ఫంక్షన్‌ని ఉపయోగించి జాబితాలో ఒక లూప్ కనుగొనబడుతుంది, ఇది లూప్‌ను తీసివేయడానికి మొదటి విధానాన్ని పిలుస్తుంది.
- ప్రధాన ఫంక్షన్‌లో ఐదు నోడ్‌లతో కొత్త లింక్ చేయబడిన జాబితా సృష్టించబడుతుంది మరియు చివరి నోడ్ యొక్క తదుపరి పాయింటర్‌ను మూడవ నోడ్‌కు సెట్ చేయడం ద్వారా లూప్ ఏర్పాటు చేయబడుతుంది.
- లింక్ చేయబడిన జాబితా యొక్క హెడ్ నోడ్‌ను ఆర్గ్యుమెంట్‌గా పాస్ చేస్తున్నప్పుడు అది “detectAndDeleteLoop” పద్ధతికి కాల్ చేస్తుంది. లూప్‌లను గుర్తించడానికి, ఈ ఫంక్షన్ 'స్లో అండ్ ఫాస్ట్ పాయింటర్స్' విధానాన్ని ఉపయోగిస్తుంది. ఇది జాబితా ఎగువన ప్రారంభమయ్యే రెండు పాయింటర్లను ఉపయోగిస్తుంది, స్లోపిటిఆర్ మరియు ఫాస్ట్‌పిటిఆర్. ఫాస్ట్ పాయింటర్ ఒకేసారి రెండు నోడ్‌లను కదిలిస్తే, స్లో పాయింటర్ ఒక సమయంలో ఒక నోడ్‌ను మాత్రమే కదిలిస్తుంది. జాబితాలో లూప్ ఉన్నట్లయితే ఫాస్ట్ పాయింటర్ చివరికి స్లో పాయింటర్‌ను అధిగమిస్తుంది మరియు రెండు పాయింట్లు ఒకే నోడ్‌లో ఢీకొంటాయి.
- ఫంక్షన్ 'deleteLoop' ఫంక్షన్‌ను లూప్‌ను కనుగొంటే, జాబితా యొక్క హెడ్ నోడ్‌ను మరియు ఇన్‌పుట్‌లుగా నెమ్మదిగా మరియు వేగవంతమైన పాయింటర్‌ల ఖండనను సరఫరా చేస్తుంది. ఈ విధానం జాబితా యొక్క హెడ్ నోడ్‌కు ptr1 మరియు ptr2 అనే రెండు పాయింటర్లను ఏర్పాటు చేస్తుంది మరియు లూప్‌లోని నోడ్‌ల సంఖ్యను గణిస్తుంది. దానిని అనుసరించి, ఇది ఒక పాయింటర్ k నోడ్‌లను అభివృద్ధి చేస్తుంది, ఇక్కడ k అనేది లూప్‌లోని మొత్తం నోడ్‌ల సంఖ్య. అప్పుడు, వారు లూప్ ప్రారంభంలో కలిసే వరకు, అది ఒక సమయంలో రెండు పాయింట్లను ఒక నోడ్‌ను ముందుకు తీసుకువెళుతుంది. లూప్ చివరిలో నోడ్ యొక్క తదుపరి పాయింటర్‌ను NULLకి సెట్ చేయడం ద్వారా లూప్ విచ్ఛిన్నమవుతుంది.
- లూప్‌ను తీసివేసిన తర్వాత, ఇది చివరి దశగా లింక్ చేయబడిన జాబితాను ప్రదర్శిస్తుంది.
విధానం 3: పునరావృతం
రికర్షన్ అనేది సమస్యలను చిన్న, సులభమైన ఉపసమస్యలుగా విభజించడం ద్వారా వాటిని పరిష్కరించే సాంకేతికత. జాబితాలోని తదుపరి నోడ్ కోసం ఒక ఫంక్షన్‌ను నిరంతరం అమలు చేయడం ద్వారా లూప్ కనుగొనబడిన సందర్భంలో ఒకే లింక్ చేయబడిన జాబితాను దాటడానికి పునరావృతం ఉపయోగించబడుతుంది.
ఏకంగా లింక్ చేయబడిన జాబితాలో, లూప్‌ను కనుగొనడానికి రికర్షన్‌ని ఉపయోగించడం వెనుక ఉన్న ప్రాథమిక సూత్రం ఏమిటంటే, జాబితా యొక్క హెడ్‌లో ప్రారంభించడం, ప్రస్తుత నోడ్‌ను ప్రతి దశలో సందర్శించినట్లు గుర్తించడం, ఆపై ఫంక్షన్‌ను పునరావృతంగా ప్రారంభించడం ద్వారా తదుపరి నోడ్‌కు వెళ్లడం ఆ నోడ్. పద్ధతి పూర్తి లింక్ చేయబడిన జాబితాపై పునరావృతమవుతుంది ఎందుకంటే ఇది పునరావృతంగా పిలువబడుతుంది.
మునుపు సందర్శించినట్లు గుర్తించబడిన నోడ్ ఫంక్షన్ ద్వారా ఎదురైతే జాబితా లూప్‌ను కలిగి ఉంటుంది; ఈ సందర్భంలో, ఫంక్షన్ నిజమైన రిటర్న్ చేయవచ్చు. లూప్ లేదని సూచించే సందర్శించిన నోడ్‌లో రన్ చేయకుండా జాబితా ముగింపుకు చేరుకున్నట్లయితే పద్ధతి తప్పుగా తిరిగి వస్తుంది.
ఒకే లింక్ చేయబడిన జాబితాలో లూప్‌ను కనుగొనడానికి రికర్షన్‌ని ఉపయోగించడం కోసం ఈ సాంకేతికత ఉపయోగించడానికి మరియు అర్థం చేసుకోవడానికి సూటిగా ఉన్నప్పటికీ, సమయం మరియు స్థలం సంక్లిష్టత పరంగా ఇది అత్యంత ప్రభావవంతమైనది కాకపోవచ్చు.
పై పద్ధతి కోసం C++ ప్రోగ్రామ్ అమలు (పునరావృతం):
#
నేమ్‌స్పేస్ stdని ఉపయోగించడం;
struct నోడ్ {
int డేటా;
నోడ్ * తరువాత;
బూల్ సందర్శించారు;
} ;
// లింక్ చేయబడిన జాబితా లూప్ గుర్తింపు ఫంక్షన్
bool detectLoopLinkedList ( నోడ్ * తల నోడ్ ) {
ఉంటే ( headNode == NULL ) {
తిరిగి తప్పుడు ; // లింక్ చేయబడిన జాబితా ఖాళీగా ఉంటే, ప్రాథమికమైనది కేసు
}
// ఒక లూప్ ఉంది ఉంటే ప్రస్తుత నోడ్ కలిగి ఉంది
// ఇప్పటికే సందర్శించారు.
ఉంటే ( తల నోడ్- > సందర్శించారు ) {
తిరిగి నిజం ;
}
// ప్రస్తుత నోడ్‌కు సందర్శన గుర్తును జోడించండి.
తల నోడ్- > సందర్శించిన = నిజం ;
// కోడ్‌కి కాల్ చేస్తోంది కోసం తదుపరి నోడ్ పదేపదే
తిరిగి లూప్‌లింక్డ్‌లిస్ట్ కనుగొనండి ( తల నోడ్- > తరువాత ) ;
}
పూర్ణాంక ప్రధాన ( ) {
నోడ్ * headNode = కొత్త నోడ్ ( ) ;
నోడ్ * secondNode = కొత్త నోడ్ ( ) ;
నోడ్ * మూడవ నోడ్ = కొత్త నోడ్ ( ) ;
తల నోడ్- > డేటా = 1 ;
తల నోడ్- > తదుపరి = రెండవ నోడ్;
తల నోడ్- > సందర్శించిన = తప్పుడు ;
రెండవ నోడ్- > డేటా = 2 ;
రెండవ నోడ్- > తదుపరి = మూడవ నోడ్;
రెండవ నోడ్- > సందర్శించిన = తప్పుడు ;
మూడవ నోడ్- > డేటా = 3 ;
మూడవ నోడ్- > తదుపరి = NULL; // లూప్ లేదు
మూడవ నోడ్- > సందర్శించిన = తప్పుడు ;
ఉంటే ( లూప్‌లింక్డ్‌లిస్ట్ కనుగొనండి ( తల నోడ్ ) ) {
కోట్ << 'లింక్ చేయబడిన జాబితాలో లూప్ కనుగొనబడింది' << endl;
} లేకపోతే {
కోట్ << 'లింక్ చేయబడిన జాబితాలో లూప్ కనుగొనబడలేదు' << endl;
}
// ఒక లూప్ సృష్టిస్తోంది
మూడవ నోడ్- > తదుపరి = రెండవ నోడ్;
ఉంటే ( లూప్‌లింక్డ్‌లిస్ట్ కనుగొనండి ( తల నోడ్ ) ) {
కోట్ << 'లింక్ చేయబడిన జాబితాలో లూప్ కనుగొనబడింది' << endl;
} లేకపోతే {
కోట్ << 'లింక్ చేయబడిన జాబితాలో లూప్ కనుగొనబడలేదు' << endl;
}
తిరిగి 0 ;
}
అవుట్‌పుట్:
లూప్ కనుగొనబడలేదు లో లింక్ చేయబడిన జాబితా
లూప్ కనుగొనబడింది లో లింక్ చేయబడిన జాబితా
వివరణ:
-
- ఫంక్షన్ డిటెక్ట్‌లూప్‌లింక్డ్‌లిస్ట్() ఈ ప్రోగ్రామ్‌లో లింక్ చేయబడిన జాబితా యొక్క హెడ్‌ని ఇన్‌పుట్‌గా అంగీకరిస్తుంది.
- లింక్ చేయబడిన జాబితా అంతటా పునరావృతం చేయడానికి ఫంక్షన్ ద్వారా పునరావృతం ఉపయోగించబడుతుంది. పునరావృతం కోసం ప్రాథమిక సందర్భంలో, ఇది ప్రస్తుత నోడ్ NULL కాదా అని నిర్ణయించడం ద్వారా ప్రారంభమవుతుంది. అలా అయితే, పద్ధతి తప్పుగా చూపబడుతుంది, ఇది లూప్ లేదని సూచిస్తుంది.
- ప్రస్తుత నోడ్ యొక్క 'సందర్శించిన' ఆస్తి విలువ అది గతంలో సందర్శించబడిందో లేదో చూడటానికి తనిఖీ చేయబడుతుంది. లూప్ కనుగొనబడిందని సూచిస్తూ, దాన్ని సందర్శించినట్లయితే అది నిజమవుతుంది.
- ఫంక్షన్ ప్రస్తుత నోడ్‌ను దాని “సందర్శించిన” ప్రాపర్టీని ట్రూగా మార్చడం ద్వారా ఇప్పటికే సందర్శించినట్లయితే సందర్శించినట్లు గుర్తు చేస్తుంది.
- సందర్శించిన వేరియబుల్ విలువ ప్రస్తుత నోడ్ ఇంతకు ముందు సందర్శించబడిందో లేదో చూడటానికి తనిఖీ చేయబడుతుంది. ఇది ఇంతకు ముందు ఉపయోగించబడి ఉంటే, లూప్ తప్పనిసరిగా ఉండాలి మరియు ఫంక్షన్ నిజమైనదిగా చూపబడుతుంది.
- చివరగా, ఫంక్షన్ పాస్ చేయడం ద్వారా జాబితాలోని తదుపరి నోడ్‌తో కాల్ చేస్తుంది headNode->తదుపరి వాదనగా. పునరావృతంగా , ఇది లూప్ కనుగొనబడే వరకు లేదా అన్ని నోడ్‌లను సందర్శించే వరకు నిర్వహించబడుతుంది. అంటే, లింక్ చేయబడిన జాబితాలోని కింది నోడ్‌కు పునరావృతంగా కాల్ చేసే ముందు ప్రస్తుత నోడ్‌ను ఎన్నడూ సందర్శించనట్లయితే, ఫంక్షన్ సందర్శించిన వేరియబుల్‌ను ట్రూగా సెట్ చేస్తుంది.
- కోడ్ మూడు నోడ్‌లను నిర్మిస్తుంది మరియు వాటిలో లింక్ చేయబడిన జాబితాను రూపొందించడానికి వాటిని కలుపుతుంది ప్రధాన విధి . పద్దతి డిటెక్ట్‌లూప్‌లింక్డ్‌లిస్ట్() తర్వాత జాబితా యొక్క హెడ్ నోడ్‌లో సూచించబడుతుంది. కార్యక్రమం ఉత్పత్తి చేస్తుంది ' లింక్ చేయబడిన జాబితాలో లూప్ తీసివేయబడింది ” ఉంటే డిటెక్ట్‌లూప్‌లింక్డ్‌లిస్ట్() నిజాన్ని తిరిగి ఇస్తుంది; లేకపోతే, అది అవుట్‌పుట్ చేస్తుంది' లింక్ చేసిన జాబితాలో లూప్ ఏదీ కనుగొనబడలేదు '.
- చివరి నోడ్ యొక్క తదుపరి పాయింటర్‌ను రెండవ నోడ్‌కు సెట్ చేయడం ద్వారా కోడ్ లింక్ చేయబడిన జాబితాలోకి లూప్‌ను చొప్పిస్తుంది. అప్పుడు, ఫంక్షన్ యొక్క ఫలితాన్ని బట్టి, అది నడుస్తుంది డిటెక్ట్‌లూప్‌లింక్డ్‌లిస్ట్() మళ్ళీ మరియు ఉత్పత్తి చేస్తుంది ' లింక్ చేయబడిన జాబితాలో లూప్ తీసివేయబడింది 'లేదా' లింక్ చేసిన జాబితాలో లూప్ ఏదీ కనుగొనబడలేదు .'
విధానం 4: స్టాక్‌ని ఉపయోగించడం
లింక్ చేయబడిన జాబితాలోని లూప్‌లను స్టాక్ మరియు “డెప్త్-ఫస్ట్ సెర్చ్” (DFS) పద్ధతిని ఉపయోగించి కనుగొనవచ్చు. లింక్ చేయబడిన జాబితా ద్వారా పునరావృతం చేయడం ప్రాథమిక భావన, ప్రతి నోడ్‌ను ఇప్పటికే సందర్శించకపోతే స్టాక్‌పైకి నెట్టడం. స్టాక్‌లో ఇప్పటికే ఉన్న నోడ్ మళ్లీ ఎదురైతే లూప్ గుర్తించబడుతుంది.
ప్రక్రియ యొక్క సంక్షిప్త వివరణ ఇక్కడ ఉంది:
-
- సందర్శించిన నోడ్‌లను రికార్డ్ చేయడానికి ఖాళీ స్టాక్ మరియు వేరియబుల్‌ను సృష్టించండి.
- ఎగువ నుండి ప్రారంభించి, లింక్ చేసిన జాబితాను స్టాక్‌పైకి నెట్టండి. తల సందర్శించబడిందని గమనించండి.
- జాబితాలోని తదుపరి నోడ్‌ను స్టాక్‌పైకి నెట్టండి. ఈ నోడ్‌కు సందర్శన గుర్తును జోడించండి.
- మీరు జాబితాను దాటుతున్నప్పుడు, ప్రతి కొత్త నోడ్‌ను సందర్శించినట్లు సూచించడానికి స్టాక్‌పైకి నెట్టండి.
- మునుపు సందర్శించిన నోడ్ స్టాక్ ఎగువన ఉన్నట్లయితే, అది ఎదురైతే దాన్ని తనిఖీ చేయండి. అలా అయితే, ఒక లూప్ కనుగొనబడింది మరియు స్టాక్‌లోని నోడ్‌ల ద్వారా లూప్ గుర్తించబడుతుంది.
- స్టాక్ నుండి నోడ్‌లను పాప్ చేయండి మరియు లూప్ కనుగొనబడకపోతే జాబితాను దాటుతూ ఉండండి.
పై పద్ధతి (స్టాక్) కోసం C++ ప్రోగ్రామ్ అమలు
#
#
నేమ్‌స్పేస్ stdని ఉపయోగించడం;
struct నోడ్ {
int డేటా;
నోడ్ * తరువాత;
} ;
// లూప్‌ను గుర్తించే ఫంక్షన్ లో లింక్ చేయబడిన జాబితా
bool detectLoopLinkedList ( నోడ్ * తల నోడ్ ) {
స్టాక్ < నోడ్ *> స్టాక్;
నోడ్ * టెంప్నోడ్ = హెడ్‌నోడ్;
అయితే ( టెంప్నోడ్ ! = శూన్యం ) {
// ఉంటే స్టాక్ యొక్క అగ్ర మూలకం సరిపోలుతుంది
// ప్రస్తుత నోడ్ మరియు స్టాక్ ఖాళీగా లేదు
ఉంటే ( ! స్టాక్.ఖాళీ ( ) && స్టాక్.టాప్ ( ) == టెంప్నోడ్ ) {
తిరిగి నిజం ;
}
స్టాక్.పుష్ ( టెంప్నోడ్ ) ;
టెంప్నోడ్ = టెంప్నోడ్- > తరువాత;
}
తిరిగి తప్పుడు ;
}
పూర్ణాంక ప్రధాన ( ) {
నోడ్ * headNode = కొత్త నోడ్ ( ) ;
నోడ్ * secondNode = కొత్త నోడ్ ( ) ;
నోడ్ * మూడవ నోడ్ = కొత్త నోడ్ ( ) ;
తల నోడ్- > డేటా = 1 ;
తల నోడ్- > తదుపరి = రెండవ నోడ్;
రెండవ నోడ్- > డేటా = 2 ;
రెండవ నోడ్- > తదుపరి = మూడవ నోడ్;
మూడవ నోడ్- > డేటా = 3 ;
మూడవ నోడ్- > తదుపరి = NULL; // లూప్ లేదు
ఉంటే ( లూప్‌లింక్డ్‌లిస్ట్ కనుగొనండి ( తల నోడ్ ) ) {
కోట్ << 'లింక్ చేయబడిన జాబితాలో లూప్ కనుగొనబడింది' << endl;
} లేకపోతే {
కోట్ << 'లింక్ చేయబడిన జాబితాలో లూప్ కనుగొనబడలేదు' << endl;
}
// ఒక లూప్ సృష్టిస్తోంది
మూడవ నోడ్- > తదుపరి = రెండవ నోడ్;
ఉంటే ( లూప్‌లింక్డ్‌లిస్ట్ కనుగొనండి ( తల నోడ్ ) ) {
కోట్ << 'లింక్ చేయబడిన జాబితాలో లూప్ కనుగొనబడింది' << endl;
} లేకపోతే {
కోట్ << 'లింక్ చేయబడిన జాబితాలో లూప్ కనుగొనబడలేదు' << endl;
}
అవుట్‌పుట్:
లూప్ కనుగొనబడలేదు లో లింక్ చేయబడిన జాబితా
లూప్ కనుగొనబడింది లో లింక్ చేయబడిన జాబితా
వివరణ:
ఈ ప్రోగ్రామ్ ఏకంగా లింక్ చేయబడిన జాబితాలో లూప్ ఉందో లేదో తెలుసుకోవడానికి స్టాక్‌ను ఉపయోగిస్తుంది.
- 1. ఇన్‌పుట్/అవుట్‌పుట్ స్ట్రీమ్ లైబ్రరీ మరియు స్టాక్ లైబ్రరీ రెండూ మొదటి లైన్‌లో ఉన్నాయి.
2. స్టాండర్డ్ నేమ్‌స్పేస్ రెండవ పంక్తిలో చేర్చబడింది, ఇన్‌పుట్/అవుట్‌పుట్ స్ట్రీమ్ లైబ్రరీ ఫంక్షన్లను “std::”తో ప్రిఫిక్స్ చేయకుండా యాక్సెస్ చేయడానికి మమ్మల్ని అనుమతిస్తుంది.
3. కింది లైన్ స్ట్రక్ట్ నోడ్‌ను నిర్వచిస్తుంది, ఇందులో ఇద్దరు సభ్యులు ఉంటారు: “డేటా” అని పిలువబడే పూర్ణాంకం మరియు “తదుపరి” అని పిలువబడే మరొక నోడ్‌కి పాయింటర్.
4. లింక్ చేయబడిన జాబితా హెడ్ అనేది డిటెక్ట్‌లూప్‌లింక్డ్‌లిస్ట్() పద్ధతికి ఇన్‌పుట్, ఇది తదుపరి లైన్‌లో నిర్వచించబడింది. ఫంక్షన్ లూప్ కనుగొనబడిందో లేదో సూచించే బూలియన్ విలువను ఉత్పత్తి చేస్తుంది.
5. 'స్టాక్' అని పిలువబడే నోడ్ పాయింటర్‌ల స్టాక్ మరియు హెడ్‌నోడ్ విలువతో ప్రారంభించబడిన 'టెంప్నోడ్' అనే నోడ్‌కు పాయింటర్ రెండూ ఫంక్షన్ లోపల సృష్టించబడతాయి.
6. అప్పుడు, టెంప్నోడ్ శూన్య పాయింటర్ కానంత వరకు, మనం కాసే లూప్‌ని నమోదు చేస్తాము.
(ఎ) స్టాక్‌లోని టాప్ ఎలిమెంట్, అది ఖాళీగా లేదని మేము నిర్ధారించడానికి ప్రస్తుత నోడ్‌తో సరిపోలాలి. లూప్ కనుగొనబడినందున మేము ఇదే జరిగితే నిజమని తిరిగి ఇస్తాము.
(బి) పైన పేర్కొన్న షరతు తప్పు అయితే, ప్రస్తుత నోడ్ పాయింటర్ స్టాక్‌పైకి నెట్టబడుతుంది మరియు టెంప్నోడ్ లింక్ చేయబడిన జాబితాలో కింది నోడ్‌కు సెట్ చేయబడుతుంది.
7. లూప్ ఏదీ గమనించబడనందున మేము while లూప్ తర్వాత తప్పుగా తిరిగి వస్తాము.
8. మేము మూడు నోడ్ ఆబ్జెక్ట్‌లను నిర్మిస్తాము మరియు వాటిని మెయిన్ () ఫంక్షన్‌లో ప్రారంభించాము. మొదటి ఉదాహరణలో లూప్ లేనందున, మేము ప్రతి నోడ్ యొక్క 'తదుపరి' పాయింటర్లను సరిగ్గా సెట్ చేస్తాము.
ముగింపు:
ముగింపులో, లింక్ చేయబడిన జాబితాలోని లూప్‌లను గుర్తించే ఉత్తమ పద్ధతి నిర్దిష్ట ఉపయోగ సందర్భం మరియు సమస్య యొక్క పరిమితులపై ఆధారపడి ఉంటుంది. హాష్ టేబుల్ మరియు ఫ్లాయిడ్ యొక్క సైకిల్-ఫైండింగ్ అల్గోరిథం సమర్థవంతమైన పద్ధతులు మరియు అవి ఆచరణలో విస్తృతంగా ఉపయోగించబడుతున్నాయి. స్టాక్ మరియు రికర్షన్ తక్కువ సమర్థవంతమైన పద్ధతులు, కానీ అవి మరింత స్పష్టమైనవి.