Ho letto alcune domande dell'intervista online su come troveremmo se ci fosse un ciclo in una lista collegata, e la soluzione (algoritmo di ricerca del ciclo di Floyd) è di avere due puntatori, uno è 2x più veloce dell'altro e controlla se si incontrano di nuovo.Algoritmo di rilevamento loop elenco collegato
La mia domanda è: perché non posso semplicemente mantenere un puntatore fisso, basta spostare l'altro puntatore in avanti di 1 passo ogni volta?
Poiché il primo puntatore (non in movimento) potrebbe non trovarsi all'interno del loop, quindi i puntatori non si incontreranno mai. (Ricordare che un loop può essere costituito solo da una parte dell'elenco.)
Questo è chiaro. Grazie a tutti, poiché posso segnare solo una risposta corretta segnerò la prima. –
Poiché il loop non può contenere l'elemento puntato dal primo puntatore.
Ad esempio, se il primo puntatore punta all'elemento 1 e l'elenco collegato ha un ciclo successivo (1-> 2-> 3-> 4-> 2), l'algoritmo non lo rileva.
abbiamo appena rimosso alcuni errori di battitura minori in modo da poterti dare gli oltre 50 in una settimana con una buona coscienza (dato che ti sei perso l'accettazione di un paio di secondi). – DaveFar
@DaveBall Wow. Grazie. Sono contento che tu abbia notato. ;) – quasiverse
Perché forse non la lista completa è all'interno del ciclo.
Per una lista collegata lazo algoritmo di rilevamento, avete bisogno di due puntatori:
Finché il primo puntatore è dove il cowboy è, non viene rilevato alcun loop. Ma se lo sposti gradualmente, alla fine entrerà nel ciclo.
BTW, lasso è il terminus technicus della teoria dei grafi, cowboy no.
C'è una modifica leggermente più veloce dell'algoritmo, se qualcuno è curioso: http://www.siafoo.net/algorithm/11 – Dave