Return a deep copy of the list.
解题思路：
这题还是挺巧妙的。由于每个node有一个指向随机结点的指针，而要找到此随机结点事很困难的。如果按照传统思路，新旧linkedlist分别为两个独立的linkedlist, 那对于新的linkedlist中的每个node来说，我们只知道对应的node在原来的linkedlist里指向的random 的node. 这是非常困难的，这的记住每个random node 在linkedlist 中的index, 这是非常复杂的。
所以，如果我们想到将新的node放到原来的linkedlist里，然后每个新的node都在对应旧的node的后面一位，那么我们就能很容易的找到新的random node了。因为每个新点的random node就是旧点的random node 的下一位。
总结下来，我们有三步：
1. copy the node
2. copy the random pointer
3. decouple the new linkedlist
Java Code:
public RandomListNode copyRandomList(RandomListNode head) {
RandomListNode safehead = new RandomListNode(0);
RandomListNode currP = head;
//copy the node
while(currP != null){
RandomListNode tmp = new RandomListNode(currP.label);
tmp.next = currP.next;
currP.next = tmp;
currP = tmp.next;
}
currP = head;
//copy the random pointer
while(currP != null){
if(currP.random != null){
currP.next.random = currP.random.next;
}
currP = currP.next.next;
}
//decouple the list
RandomListNode p = safehead;
currP = head;
while(currP != null){
p.next = currP.next;
currP.next = currP.next.next;
currP = currP.next;
p = p.next;
}
return safehead.next;
}
