A takie cos:
a) pierwsza iteracja: robimy prosta kopie oryginalnej listy, przypisujac odpowiednio next kopiowanym wezlom, rand pozostawiajac pusty; dodatkowo, budujemy 2 struktury:
- pierwsza, 'identity hash map', gdzie kluczem jest wezel z oryginalnej listy, a wartoscia jego kolejnosc / indeks w liscie
- druga to tablica o wielkosci listy, gdzie kazdemu indeksowi przypisujemy wezel ktory na tej pozycji lezy w nowej liscie. Robimy to po to aby miec tymczasowy 'random access' O(1) w liscie laczonej.
b) druga iteracja: jednoczesnie iterujemy po obu listach, zmieniajac synchronicznie aktualnie przetwarzane elementy z obu list. Z oryginalnej listy bierzemy dla kazdego elementu jego element rand, wyszukujemy go w tej 'pierwszej' mapie i mamy jego indeks w liscie. Teraz z 'drugiej' tablicy za pomoca tego indeksu bierzemy wezel (czas O(1), zamiast latac po liscie i zliczac ciagle, co byloby katastrofa w Big Oh), ktory bedzie wezlem rand w nowej liscie, i go ustawiamy jako rand dla aktualnego elementu kopii w danej iteracji.
Wydaje mi sie ze to bedzie dzialac. Roznice z pierwsza odpowiedzia:
a) dwukrotnie wieksze zuzycie pamieci (dodatkowa mapa oraz tablica), ale nadal stale bo zalezne tylko od ilosci wezlow oryginalnej listy (zdaje mi sie, chociaz specem nie jestem, prosze o sprostowanie jesli sie myle)
b) oryginalna lista nie ulega zniszczeniu, pozostaje nie zmieniona - nie wiem czy to ma jakiekolwiek znaczenie, w zadaniu nie ma o tym slowa, ale wydaje mi sie ze mogloby to byc pomocne, i poza tym chcialem sprobowac wlasnie zrobic cos co nie niszczy oryginalu
Prosze o uwagi ;d