copy link with random additional pointers

copy link with random additional pointers
copy linked list。 each node has two pointers，one is poiting to next, the other is random, find a algorithm in O(n) time ，NO EXTRA RAM，copy this linked list。
-------------------------------------------------------------

(imagine you have a->b->c->d, lets call the other pointer as "other"

1. duplicate each node and insert after itself. Now you get a->a->b->b->c->c->d->d

2. node n=head
while(n!=null)
n->next->other = n->other->next
n=n->next->next

3. separate the two lists
head2 = head->next
node n=head
while(n->next->next !=null)
n->next->next = n->next->next->next
n->next = n->next->next
n=n->next
n->next = null
n->next->next = null