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

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

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

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

Node *copyList(Node *head)
{
    for (Node* cur = head; cur != NULL; cur = cur->next) {
        Node* dup = (Node*)malloc(sizeof(Node));
        dup->data = cur->data;
        dup->next = cur->random;
        cur->random = dup;
    }
    Node* result = head->random;
    for (Node* cur = head; cur != NULL; cur = cur->next) {
        Node* dup = cur->random;
        dup->random = dup->next->random;
    }
    for (Node* cur = head; cur != NULL; cur = cur->next) {
        Node* dup = cur->random;
        cur->random = dup->next;
        dup->next = cur->next ? cur->next->random : NULL;
    }
    return result;
}