W dniu 2011-06-15 08:19, Wojciech "Spook" Sura pisze:
> Hej!
>
> Kolega zaproponował zadanie: w jaki sposób odnaleźć cykl w liście
> jednokierunkowej nie niszcząc jej, zachowując stałe zużycie pamięci i w
> czasie liniowym?


Ale odnaleźć cykl oznacza wypisać wszystkie elementy cyklu,
rownoważnie znaleźć jakikolwiek element cyklu, czy
znaleźć element 'wejściowy'?

Jeśli to pierwsze, to:

Masz dwa iteratory, biegacza i wartownika.

ustalasz wartownika na pierwszym elemencie,
nastepnie w pętli k =1,2...
Niech biagacz przeiteruje 2^k elementów liczac
od wartownika. Jesli natrafił na wartownika
(petla) lub koniec listy, kończymy pętle.
Jeśli nie, ustawiamy wartownika na ostatniej
pozycji biegacza.

Jeśli nie było ślepego końca, biegniemy
ostatni raz w kolko po cyklu wypisując składowe.


Wartownika postawimy na cyklu po co najwyzej 2n ruchach
biegacza. Dodatkowe n na ostatnie przejście cyklu,
łącznie zrobimy 3*n operacji przesuniecie biegacza + test warunku.

Jak wyznaczyć 'pierwszy' element cyklu liniowo w stałej pamięci
nie mam pomysłu.

> Mam pewien pomysł, ale niestety przy liniowym zużyciu pamięci, nijak nie
> umiem zejść do stałego. Macie jakieś pomysły?

Podejrzewam, że to ten sam tylko założyłeś od razu trudniejszą
wersje problemu.

pozdrawiam
bartekltg