Come determinare se un elenco collegato contiene un ciclo?

Question

Possibili duplicati:
find whether a loop in a linked list without two pointers
How to determine if a linked list has a cycle using only two memory locations.
Best algorithm to test if a linked list has a cycle

Durante una preparazione per un colloquio di lavoro, ho incontrato alla seguente domanda:

Come è possibile determinare se un l'elenco collegato (di qualsiasi tipo) contiene un ciclo, usando additio la complessità dello spazio nale di O (1)? Non si può presumere che il ciclo inizi dal primo nodo (e, naturalmente, il ciclo non deve contenere tutti i nodi).

non riuscivo a trovare la risposta, anche se ho la sensazione è abbastanza semplice ...

Answer 1

facile. Mantieni due puntatori nella lista. Ad ogni passo, fai avanzare un puntatore con un singolo collegamento e fai avanzare l'altro di due collegamenti. Prova a vedere se puntano allo stesso elemento. Se è così, hai un ciclo. In caso contrario, ripetere fino a trovare un ciclo o si raggiunge la fine della lista.

Answer 2

Probabilmente la stessa tecnica utilizzata per verificare se un grafico è un albero (gli alberi non possono avere cicli), vedere this this question. Raccomanda un ordinamento topologico o una prima ricerca di profondità.

Answer 3

Ho avuto questo problema esatto in vero codice dal vivo la scorsa settimana.

Tutto ciò che ho fatto è stato mantenuto un puntatore (collegamento) per il primo elemento. Poi, mentre scorrevo l'elenco, se avessi di nuovo puntato quel puntatore, so che c'è un loop.