Copy List with Random Pointer

12/27/2017 update
1. have to check random == null when match random.
2. original list can not be modified.
--------------------------------------------------------------------
思路：
2种方法

1. hash map
key是old node, value是新node。然后再匹配next和random。空间复杂度是O(n)
2. O(1)
1->2->3->null 变成1->1'->2->2'->3->3'->null，然后拷贝random，最后split。

实现：
第二种方法split说一下。需要一个temp node来迭代新的 linkedlist。每一次取node.next.next的时候，要坚持node.next是否为空。代码如下：

 /**  
  * Definition for singly-linked list with a random pointer.  
  * class RandomListNode {  
  *   int label;  
  *   RandomListNode next, random;  
  *   RandomListNode(int x) { this.label = x; }  
  * };  
  */  
 public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null){  
       return null;  
     }  
        head = insert(head);
        head = matchRandom(head);
        return split(head);
    }

    private RandomListNode insert(RandomListNode head) {
      RandomListNode dummy = new RandomListNode(0);
      dummy.next = head;
      while (head != null) {
        RandomListNode copy = new RandomListNode(head.label);
        copy.next  =  head.next;
        head.next = copy;
        head = head.next.next;
      }
      return dummy.next;
    }

    private RandomListNode matchRandom(RandomListNode head) {
      RandomListNode dummy = new RandomListNode(0);
      dummy.next = head;
      while (head != null) {
        if (head.random != null) {
            head.next.random = head.random.next;    
        }
        head = head.next.next;
      }

      return dummy.next;
    }

    private RandomListNode split(RandomListNode  head) {
      RandomListNode  newHead =  head.next;
      while (head != null) {
        RandomListNode copy = head.next;
        head.next = copy.next;
        head = head.next;
        copy.next = (head != null) ? head.next : null;
      }

      return newHead;
    }
}