LC 138

两种方法：

**方案一：**

两次遍历，第一次入map map中存

*原来的节点*

和

*copy的节点*

得key value对

第二次遍历，使用map链接 next 和random

时间2n O（n） 空间n

**方案二：**

1->2->3->null 1->1'->2->2'->3->3'->null

三次遍历： 第一次遍历链接next 第二次遍历链接random 第三次拆分 链表

时间O(3n)=O(n) 空间O(1)