[LeetCode]Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
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;
    }