Anonymní profil Shaolin – Programujte.com

Tak už jsem to vyřešil. V tom for cyklu je třeba obdélníky vytvářet dynamicky. Takže teď to volám takto: seznam.vloz(new Obdelnik(1, 2, 3, 4); diky

Jinak už jsem zjistil, že se jedná o využití algoritmu želvy a zajíce. Viz: http://en.wikipedia.org/wiki/Floyd%27s_cycle-finding_algorithm#Tortoise_and_hare

To je pravda, takhle to nepůjde.

Díky za podrobný rozbor :-)
K 1 příspěvku: Všechna ta řešení nejsou použitelná, protože v zadání je uvedeno použít konstantní velikost pomocného pole. Jedině tedy vyhovuje řešení číslo 4. To je přesně to samé, které navrhl KIIV.
K 2 příspěvku: Jedná se o takový rébus. Je tedy nutné se odprostit od praktických řešení ;-) Přidávat prvky do seznamu je možné. Je ale nutné, aby seznam na konci algoritmu byl stejný jako na začátku.

Zjišťuju ale, že moje řešení možná také není správné, protože možná nevyhovuji zadání na konstantním pomocné pole. Počet pomocných zarážek bude totiž závislý na délce pole.

Vypadá to že jediné 100% řešení je to první od KIIV (tvůj bod 4). Připadá mi to ale dost neefektivní, tak se snažím vymyslet něco efektivnějšího. Možná kdyby se ty zarážky nevytvářely pravidelně ale třeba pomocí násobku dvou. Tedy první zarážka třeba 4 a další pak 8, 16, 32, 64, 128, 256 atd... U seznamu s milionem prvků bych se dostal na počet 20 zarážek, které se myslím dají chápat jako konstantní číslo (i pro delší seznamy). Myslím, že cokoli trochu zlepší tu složitost O(n^2) pomůže.

Jo rozumím. Ale to nepůjde. Ten seznam už je vytvořený a nejde měnit jeho strukturu. Ale myslím, že už mám celkem šikovné řešení: S nějakou (ještě nevím přesně jakou) pravidelností budu vkládat do seznamu své vlastní zarážky. Zarážky budou mít mou vlastní strukturu, budou vzestupně číslované. Jelikož je seznam založen na odkazech na další prvky, tak to nebude problém. No a pak při procházení seznamu někdy narazím na mou vlastní zarážku. Pak vím, že už jsem v cyklu. Takže si poznamenám nějaké potřebné hodnoty a můžu začít procházet seznam od začátku a odstraňovat svoje zarážky (aby zůstal seznam po skončení algoritmu stejný jako na začátku). Pokud budu vkládat svůj prvek po každém desátém prvku v seznamu, tak mi stačí si poznamenat do pomocného konstantního pole těch 10 prvků v seznamu, na které musí odkazovat poslední prvek v seznamu a ty kontrolovat, než dojdu na konec.
To je základ. Možná by ten konec šel udělat ještě lépe, ale obecně by to mělo mít lepší časovou náročnost. Každopádně díky za rady, pomohlo mi to se držet určitého správného směru.