35. 复制复杂链表

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

提示： -10000 <= Node.val <= 10000Node.random 为空（null）或指向链表中的节点。节点数目不超过 1000 。

思路

1. 使用哈希表来存储结点 [O(1)访问]
2. 第一遍遍历
   1. 先生成具有val属性的链表(哈希存储之后就可很方便访问了)
      1. **map.set(cur, new Node(cur.val))**
      2. cur = cur.next
3. cur回到头节点
   1. cur = head
4. 第二遍遍历
   1. 据map映射关系，将random和next指针指向对应的节点或者null
      1. **map.get(cur).next = map.get(cur.next) || null**
      2. map.get(cur).random = map.get(cur.random) || null
      3. cur = cur.next

5. 返回链表的头

   1. return map.get(head); ```javascript var copyRandomList = function (head) { if (!head) return head;

   let cur = head; const map = new Map(); // 第一次遍历，生成一个具有val属性的链表； while (cur) { map.set(cur, new Node(cur.val)) cur = cur.next } //第二次遍历，根据map映射关系，将random和next指针指向对应的节点或者null; cur = head while (cur) { map.get(cur).next = map.get(cur.next) || null map.get(cur).random = map.get(cur.random) || null cur = cur.next } return map.get(head); };

```