Task on list copying

There is a unidirectional list of structures. In it, random points to some other element of the same list. You need to write a function that copies this list with saving the structure (in case the first node’s random pointed to the 4th in the old list, the new list should be the same – the random of the first node points to the 4th node of the new list). Here you can use O(n), constant additional memory, and memory for the new list elements. It is not allowed to allocate memory for all the data by one block. Thus, the list should be honest, scattered in parts, and not a single block, like an array.

Here we want to provide you with one of the solution options. Thus, we pass through the list, create duplicates of nodes and insert them by next. This way, we get 2*N elements and each odd one makes reference to its duplicate. 

Then, we make the second list pass-through. In each even node random = random.text. Then we make the third list pass-through, next is equal to next.next in each node.  

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;
}