Upptäck en loop i en länkad lista i C++

Slutnoden på en länkad lista som har en loop kommer att referera till en annan nod i samma lista snarare än NULL. Om det finns en nod i en länkad lista som kan nås upprepade gånger genom att följa nästa pekare, sägs listan vara ha en cykel.

Vanligtvis hänvisar den länkade listans sista nod till en NULL-referens för att beteckna listans slutsats. Men i en länkad lista med en slinga hänvisar listans slutnod till en startnod, en intern nod eller sig själv. Under sådana omständigheter måste vi därför identifiera och avsluta slingan genom att ställa in nästa nods referens till NULL. Detekteringsdelen av slingan i en länkad lista förklaras i den här artikeln.

I C++ finns det många sätt att hitta loopar i en länkad lista:

Hash-tabellbaserad metod : Detta tillvägagångssätt lagrar adresserna till besökta noder i en hashtabell. En loop i den länkade listan finns om en nod redan finns i hashtabellen när den besöks igen.

Floyds cykelstrategi : Algoritmen för 'sköldpadda och hare', allmänt känd som Floyds cykelsökningsalgoritm: Denna teknik använder sig av två pekare, den ena rör sig långsammare än den andra och den andra går snabbare. Den snabbare pekaren kommer i slutändan att gå om den långsammare pekaren om det finns en slinga i den länkade listan, vilket avslöjar slingans existens.

Rekursiv metod : Denna metod går igenom den länkade listan genom att anropa sig själv om och om igen. Den länkade listan innehåller en loop om den aktuella noden tidigare har besökts.

Stackbaserat tillvägagångssätt : Detta tillvägagångssätt lagrar adresserna till besökta noder i en stack. En slinga i den länkade listan finns om en nod redan finns där i stacken när den besöks igen.

Låt oss förklara varje tillvägagångssätt i detalj för att förstå konceptet.

Metod 1: HashSet-metoden

Att använda hash är den enklaste metoden. Här går vi igenom listan en efter en samtidigt som vi håller en hashtabell med nodadresserna. Därför existerar en loop om vi någonsin kör över nästa adress för den aktuella noden som redan finns i hashtabellen. Annars finns det ingen loop i den länkade listan om vi stöter på NULL (dvs. når slutet av den länkade listan).

Det kommer att vara ganska enkelt att implementera denna strategi.

När vi går igenom den länkade listan kommer vi att använda en unordered_hashmap och fortsätta lägga till noder till den.

När vi nu stöter på en nod som redan visas på kartan kommer vi att veta att vi har kommit till slingans början.

• • Dessutom höll vi två pekare vid varje steg, headNode pekar på den aktuella noden och lastNode pekar på den tidigare noden för den aktuella noden, medan den itererar.
  • Som vår headNode pekar nu på startnoden för slingan och som lastNode pekade på noden som huvudet pekade på (dvs det syftar på lastNode av slingan), vår headNode pekar för närvarande på slingans startnod.
  • Slingan bryts genom att ställa in l astNode->nästa == NULL .

Genom att göra detta börjar slutslingnoden istället för att referera till slingans initiala nod att peka på NULL.

Hashingmetodens genomsnittliga tid- och rymdkomplexitet är O(n). Läsaren bör alltid vara medveten om att implementeringen av den inbyggda Hashing DataStructure i programmeringsspråket kommer att avgöra den totala tidskomplexiteten i händelse av en kollision i hashing.

C++-programimplementering för ovanstående metod (HashSet):

Produktion:

Kodens steg-för-steg förklaring ges nedan:

1. 1. Rubrikfilen bits/stdc++.h>, som innehåller alla vanliga C++-bibliotek, ingår i koden.
   2. En struktur som kallas 'Node' är konstruerad, och den har två medlemmar: en referens till nästa nod i listan och ett heltal som kallas 'värde'.
   3. Med ett heltalsvärde som indata och 'nästa'-pekaren inställd på NULL, skapar funktionen 'newNode' en ny nod med det värdet.
   4. Funktionen ' functionHashMap' är definierad, vilket tar en pekare till huvudnoden för den länkade listan som indata.
   5. Inuti ' functionHashMap ', skapas en oordnad_karta med namnet 'hash_map', som används för att implementera en hashkartadatastruktur.
   6. En pekare till den sista noden i listan initieras till NULL.
   7. En while-loop används för att gå igenom den länkade listan, som börjar från huvudnoden och fortsätter tills huvudnoden är NULL.
   8. LastNode-pekaren uppdateras till den aktuella noden inuti while-slingan om den aktuella noden (headNode) inte redan finns i hashkartan.
   9. Om den aktuella noden hittas i kartan betyder det att en slinga finns i den länkade listan. För att ta bort slingan, nästa pekare av lastNode är satt till NULL och while-slingan är bruten.
   10. Den länkade listans huvudnod används som indata för en funktion som kallas 'display', som matar ut värdet för varje nod i listan från början till slut.
   11. I den huvud funktion, skapa en loop.
   12. Funktionen 'functionHashMap' anropas med headNode-pekaren som ingång, vilket tar bort slingan från listan.
   13. Den ändrade listan visas med funktionen 'display'.

Tillvägagångssätt 2: Floyds cykel

Floyds cykeldetekteringsalgoritm, ofta känd som sköldpaddan och harealgoritmen, utgör grunden för denna metod för att lokalisera cykler i en länkad lista. Den 'långsamma' pekaren och den 'snabba' pekaren, som går igenom listan med olika hastigheter, är de två pekarna som används i denna teknik. Den snabba pekaren går framåt två steg medan den långsamma pekaren går ett steg varje iteration. En cykel i den länkade listan finns om de två punkterna någonsin kommer ansikte mot ansikte.

1. Med den länkade listans huvudnod initierar vi två pekare som kallas snabb och långsam.

2. Nu kör vi en slinga för att gå igenom den länkade listan. Den snabba pekaren ska flyttas två platser framför den långsamma pekaren vid varje iterations steg.

3. Det kommer inte att finnas en loop i den länkade listan om snabbpekaren når slutet av listan (fastPointer == NULL eller fastPointer->next == NULL). Om inte, kommer de snabba och långsamma pekarna så småningom att mötas, vilket innebär att den länkade listan har en loop.

C++-programimplementering för ovanstående metod (Floyd's Cycle):

Produktion:

Förklaring:

1. 1. De relevanta rubrikerna, som 'bits/stdc++.h' och 'std::cout,' inkluderas först.
   2. 'Node'-strukturen, som står för en nod i den länkade listan, deklareras sedan. En nästa pekare som leder till följande nod i listan ingår tillsammans med ett heltalsdatafält i varje nod.
   3. Sedan definierar den 'deleteLoop' och 'detectAndDeleteLoop', två funktioner. En slinga tas bort från en länkad lista med den första metoden, och en slinga detekteras i listan med den andra funktionen, som sedan anropar den första proceduren för att ta bort slingan.
   4. En ny länkad lista med fem noder skapas i huvudfunktionen och en loop upprättas genom att den sista nodens nästa pekare ställs in på den tredje noden.
   5. Den gör sedan ett anrop till metoden 'detectAndDeleteLoop' samtidigt som den skickar den länkade listans huvudnod som ett argument. För att identifiera loopar använder den här funktionen metoden 'Långsamma och snabba pekare'. Den använder två pekare som börjar överst på listan, slowPTR och fastPTR. Medan den snabba pekaren flyttar två noder samtidigt, flyttar den långsamma pekaren bara en nod i taget. Den snabba pekaren kommer i slutändan att passera den långsamma pekaren om listan innehåller en loop, och de två punkterna kommer att kollidera vid samma nod.
   6. Funktionen anropar funktionen 'deleteLoop' om den hittar en loop, och tillhandahåller listans huvudnod och skärningspunkten mellan de långsamma och snabba pekarna som indata. Denna procedur upprättar två pekare, ptr1 och ptr2, till listans huvudnod och räknar antalet noder i slingan. Efter det flyttar den fram en pekare k-noder, där k är det totala antalet noder i slingan. Sedan, tills de möts i början av loopen, flyttar den fram båda punkterna en nod i taget. Slingan bryts sedan genom att sätta nästa pekare för noden i slutet av slingan till NULL.
   7. Efter att ha tagit bort slingan visar den den länkade listan som ett sista steg.

Tillvägagångssätt 3: Rekursion

Rekursion är en teknik för att lösa problem genom att dela upp dem i mindre, enklare delproblem. Rekursion kan användas för att gå igenom en enkellänkad lista i händelse av att en loop hittas genom att kontinuerligt köra en funktion för nästa nod i listan tills listans slut nås.

I en enkellänkad lista är grundprincipen bakom att använda rekursion för att hitta en slinga att börja längst fram i listan, markera den aktuella noden som besökt vid varje steg och sedan gå vidare till nästa nod genom att rekursivt anropa funktionen för den noden. Metoden kommer att iterera över den fullständiga länkade listan eftersom den kallas rekursivt.

Listan innehåller en loop om en nod som tidigare har markerats som besökt påträffas av funktionen; i detta fall kan funktionen returnera sant. Metoden kan returnera false om den når slutet av listan utan att köra över en besökt nod, vilket indikerar att det inte finns någon loop.

Även om denna teknik för att använda rekursion för att hitta en slinga i en enda länkad lista är enkel att använda och förstå, kanske den inte är den mest effektiva när det gäller tid och rumskomplexitet.

C++-programimplementering för ovanstående metod (Rekursion):

Produktion:

Förklaring:

1. 1. Funktionen detectLoopLinkedList() i detta program accepterar huvudet av den länkade listan som en ingång.
   2. Rekursion används av funktionen för att iterera över den länkade listan. Som grundfallet för rekursionen börjar den med att bestämma om den aktuella noden är NULL. Om så är fallet returnerar metoden false, vilket indikerar att ingen loop existerar.
   3. Värdet på den aktuella nodens 'besökta' egenskap kontrolleras sedan för att se om den tidigare har besökts. Den returnerar sant om den har besökts, vilket tyder på att en slinga har hittats.
   4. Funktionen markerar den aktuella noden som besökt om den redan har besökts genom att ändra dess 'besökta'-egenskap till true.
   5. Värdet på den besökta variabeln kontrolleras sedan för att se om den aktuella noden har besökts tidigare. Om den har använts tidigare måste en loop existera och funktionen returnerar true.
   6. Slutligen anropar funktionen sig själv med nästa nod i listan genom att passera headNode->nästa som ett argument. Rekursivt , detta utförs fram tills antingen en loop hittas eller alla noder har besökts. Betyder att funktionen ställer in den besökta variabeln till sant om den aktuella noden aldrig har besökts innan den rekursivt anropar sig själv för följande nod i den länkade listan.
   7. Koden bygger tre noder och sammanfogar dem för att skapa en länkad lista i huvudfunktion . Metoden detectLoopLinkedList() anropas sedan på listans huvudnod. Programmet producerar ' Slinga dras av i länkad lista ' om detectLoopLinkedList() returnerar sant; annars matar den ut ' Ingen loop upptäckt i länkad lista '.
   8. Koden infogar sedan en slinga i den länkade listan genom att sätta den sista nodens nästa pekare till den andra noden. Sedan, beroende på resultatet av funktionen, körs den detectLoopLinkedList() igen och producerar antingen ' Slinga dras av i länkad lista ' eller ' Ingen loop upptäckt i länkad lista .”

Tillvägagångssätt 4: Använda Stack

Slingor i en länkad lista kan hittas med hjälp av en stack och metoden 'djup-först sökning' (DFS). Det grundläggande konceptet är att iterera genom den länkade listan, skjuta varje nod till stacken om den inte redan har besökts. En slinga känns igen om en nod som redan finns på stacken påträffas igen.

Här är en kort beskrivning av proceduren:

1. 1. Skapa en tom stack och en variabel för att registrera de noder som har besökts.
   2. Skjut den länkade listan på stapeln, med början på toppen. Anteckna att huvudet har besökts.
   3. Tryck nästa nod i listan till stacken. Lägg till ett besöksmärke till denna nod.
   4. När du går igenom listan, tryck varje ny nod på stapeln för att indikera att den har besökts.
   5. Kontrollera om en nod som tidigare har besökts är överst i stacken om den påträffas. Om så är fallet har en slinga hittats och slingan identifieras av noderna i stacken.
   6. Ta bort noderna från stacken och fortsätt gå igenom listan om ingen loop hittas.

C++-programimplementering för ovanstående metod (Stack)

Produktion:

Förklaring:

Det här programmet använder en stack för att ta reda på om en enkellänkad lista har en loop.

• 1. Ingångs-/utgångsströmbiblioteket och stackbiblioteket finns båda på den första raden.

  2. Standardnamnrymden ingår i den andra raden, vilket gör att vi kan komma åt ingångs-/utgångsströmbibliotekets funktioner utan att behöva prefixet dem med 'std::.'

  3. Följande rad definierar strukturnoden, som består av två medlemmar: ett heltal som kallas 'data' och en pekare till en annan nod som heter 'nästa'.

  4. Den länkade listans huvud är en ingång för metoden detectLoopLinkedList(), som definieras på nästa rad. Funktionen producerar ett booleskt värde som indikerar om en slinga hittades eller inte.

  5. En stack med nodpekare som kallas 'stack' och en pekare till en nod med namnet 'tempNode' som initieras med värdet för headNode skapas båda inuti funktionen.

  6. Sedan, så länge som tempNode inte är en nollpekare, går vi in ​​i en while-loop.

  (a) Det översta elementet i stacken måste matcha den aktuella noden för att vi ska kunna fastställa att den inte är tom. Vi returnerar true om så är fallet eftersom en loop har hittats.

  (b) Om det förutnämnda villkoret är falskt, skjuts den aktuella nodpekaren till stacken och tempNode sätts till följande nod i den länkade listan.

  7. Vi returnerar falskt efter while-loopen eftersom ingen loop observerades.

  8. Vi bygger tre Node-objekt och initierar dem i main()-funktionen. Eftersom det inte finns någon loop i det första exemplet, ställer vi in ​​'nästa' pekare för varje nod korrekt.

Slutsats:

Sammanfattningsvis beror den bästa metoden för att upptäcka loopar i en länkad lista på det specifika användningsfallet och problemets begränsningar. Hash Table och Floyds cykelsökningsalgoritm är effektiva metoder och de används flitigt i praktiken. Stack och rekursion är mindre effektiva metoder men de är mer intuitiva.