Задача на копирование списка

Есть однонаправленный список из структур. В нём random указывает на какой-то еще элемент этого же списка. Требуется написать функцию, которая копирует этот список с сохранением структуры (т.е. если в старом списке random первой ноды указывал на 4-ю, в новом списке должно быть то же самое — рандом первой ноды указывает на 4-ю ноду нового списка). O(n), константная дополнительная память + память под элементы нового списка. Нельзя сразу выделить память под все данные одник куском т.е. список должен быть честным, разбросанным по частям, а не единым блоком, как массив.

Вот один из вариантов решения. Делаем обход списка, создаём дубликаты узлов и вставляем их по next, получая 2*N элементов, каждый нечётный ссылается на свой дубликат. Делаем второй обход списка, в каждом чётном узле random = random.next. Делаем третий обход списка, в каждом узле next = next.next.

Есть ещё один вариант от Пашки Джиоева.