Ciclo in lista concatenata

[TomSawyer1]

Propongo questo problema carino: descrivere un algoritmo che, in spazio costante e tempo lineare, decida se in una lista concatenata unidirezionale è presente un ciclo o no.

ps: un ciclo in una lista concatenata è un sottoinsieme della lista tali che ogni nodo punta al successivo e l'ultimo punta al primo.

[simo_83]

non ho capito.. bisogna far vedere che è una lista circolare???

[codino75]

che si intende per 'spazio costante' ?

[simo_83]

"codino75":che si intende per 'spazio costante' ?

suppongo debba essere fatto "sul posto", ovvero senza utilizzare strutture aggiuntive.

[_Tipper]

Sì, le complessità in spazio e tempo riguardano la memoria utilizzata e il tempo richiesto per la computazione.

[TomSawyer1]

Sì, è come dice Tipper, chiaramente.

@simo_83
Non proprio una lista circolare. La definizione che ho dato mi sembra chiara: dire se esiste un _sottoinsieme_ di nodi di una lista concatenata etc..

[codino75]

"Tipper":Sì, le complessità in spazio e tempo riguardano la memoria utilizzata e il tempo richiesto per la computazione.

intendi dire che la memori autilizzata deve essere costante rispetto alle dimensioni della lista?
cioe' lo stesso spazio qualunque sia la lunghezza della lista?
come e' possibile tutto cio'?

edit: ah, forse inizio a capire...