Duplicate a fancy linked list

Problem:
Every node of the linked list has a random pointer (in addition to the next pointer) which could randomly point to another node or be null. How would you duplicate such a linkedlist?

Solution:
* Create the copy of node 1 and insert it between node 1 & node 2 in original Linked List, create the copy of 2 and insert it between 2 & 3.. Continue in this fashion, add the copy of N afte the Nth node

* Now copy the arbitrary link in this fashion

original->next->arbitrary = original->arbitrary->next; /*TRAVERSE TWO NODES*/

This works because original->next is nothing but copy of original and
Original->arbitrary->next is nothing but copy of arbitrary.

* Now restore the original and copy linked lists in this fashion in a single loop.
original->next = original->next->next;
copy->next = copy->next->next;

* Make sure that last element of original->next is NULL.

Complexity:

time - O(n)
space - O(1)

Links and credits:
http://www.linkedin.com/groups/Every-node-linked-list-has-1920463.S.243967327?view=&gid=1920463&type=member&item=243967327&trk=eml-anet_dig-b_nd-pst_ttle-cn