[数据结构与算法]7/22每日一题

138. 复制带随机指针的链表

• 思路
  哈希+回溯，用哈希表记录每一个节点对应新节点的创建情况，遍历链表递归创建新链表，当新链表创建好了，就回溯开始添加random指针
• 代码

  class Solution {
  Map<Node,Node> map = new HashMap();
  public Node copyRandomList(Node head) {
      if(head==null)
      return null;
      if(!map.containsKey(head)){
          Node newNode = new Node(head.val);
          map.put(head,newNode);
          newNode.next=copyRandomList(head.next);
          newNode.random=copyRandomList(head.random);
      }
      return map.get(head);
  }
  

}
```