Список со случайными указателями

У вас есть связный список, в каждом узле которого хранятся две ссылки: обычная ссылка на следующий элемент и дополнительная ссылка на произвольный элемент того же списка. Пример такого списка показан на рисунке:

Здесь красным цветом выделены ссылки на следующий элемент, а синим - на случайный. Заметьте, что никаких ограничений на случайные ссылки нет: они могут указывать на тот же элемент, указывать назад, образовывать циклы и т.п.

Требуется скопировать такой список за линейное время и константную память. Если потребуется, Вы можете временно изменить оригинальный список, но потом Вам нужно будет вернуть его в исходное состояние.

Решение
Скопировать список можно за три прохода.

Шаг 1. Вставляем копии элементов между исходными элементами.

Node copy = current.copy();
copy.next = current.next;
current.next = copy;

Шаг 2. Копируем случайные указатели.

current.next.random = current.random.next;

Шаг 3. Восстанавливаем начальную структуру обоих списков:

Node currentCopy = current.next;
Node originalNext = currentCopy.next;
Node copyNext = originalNext != null ? originalNext.next : null;
current.next = originalNext;
currentCopy.next = copyNext;