A linked list where a node has two pointers，one point to next node，the other point to an random node. O(n) time，O(1) space to copy this linked list.

A linked list where a node has two pointers，one point to next node，the other point to an random node. O(n) time，O(1) space to copy this linked list.
Suppose original list is x1->x2->x3->x4…->xn
Add new nodes to original list like:
y1->x1->y2->x2->y3->x3->…->yn->xn
yi->rand=xi->rand->next// this should be yi->rand=xi->rand->prev,
So the linked list should be double linked list