Solutution to Random Pointer

Link to the Problem

Vandana gave a simple solution which was correct but it needed O(n) extra space and Anonymous got rid if that extra space and gave us an O(n) solution using constant space.
My solution is same as Anonymous'! Here it goes :

As Anonymous pointed out, the random pointer is a little too weak, so the idea is to use the next pointer to maintain correspondences between the old and the new (copy) list before assigning the random pointers for the new list!
Let the old list be
O1 --> O2 --> O3 --> O4 --> NULL
create new nodes and insert them in between the old nodes with old list's next pointing to the corresponding new node and the new node's next pointing to old's original next. So we get something like,
O1 --> N1 --> O2 --> N2 --> O3 --> N3 --> O4 --> N4 --> NULL
Also while creating the new nodes, copy the corresponding old node's data to the new node's data.
Now traverse through this list and assign current node's random pointer's next to the next node's random pointer.
Thus if O1->random was pointing to O3, then we get N1->random = O1->random->next = O3->next = N3;
Skip the alternate (new) nodes while doing this. When this traversal is done through the whole list, we have the new nodes having the exact structure as the old nodes. Hence, the only thing now left to be done is detaching the two lists, which can be easily done by storing old->next to a temporary pointer and then assigning old's next to old's next's next and similarly for the new nodes. Hence we get two lists
O1 --> O2 --> O3 --> O4 --> NULL and
N1 --> N2 --> N3 --> N4 --> NULL
with the random pointers also properly assigned!