Обращение связанного списка с узлами, имеющими случайный указатель

Недавно я столкнулся с этим интересным вопросом:

«Рассмотрите связанный список с каждым узлом, в дополнение к наличию следующего 'указатель также имеет' случайный 'указатель. «Случайный» указатель указывает на какой-то другой случайный узел в связанном списке. Он также может указывать на NULL. Чтобы упростить ситуацию, никакие два «случайных» указателя не будут указывать на один и тот же узел, но более чем 1 случайный указатель узла может указывать на NULL.

Теперь нам нужно изменить направление всех указателей (как «следующий», так и «случайный») связного списка. Ограничение состоит в том, что решение ДОЛЖНО иметь сложность пространства O (1) (может быть создано постоянное количество новых узлов, но не пропорционально длине списка) "

Я потратил довольно много времени на обдумывание этого. Я не действительно убежден, что это действительно возможно.