一、题目

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random —> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random —> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

  • val：一个表示 Node.val 的整数。
  • random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。

点击查看原题
难度级别：中等

二、思路

1）哈希

如果只是创建一个链，把next指针指对，这个很容易，可它存在了random指针，在按需复制节点过去的情况下，random可能指向还未复制过的节点，所以使用两遍遍历的方法：
第一次遍历，复制同样的节点，并将next指针赋值
第二次遍历，记录原始链表中random指向节点，根据hashmap中原始链表节点和新链表节点的映射关系，给新节点random赋值

三、代码

1）哈希

  1. class Solution {
  2.     public Node copyRandomList(Node head) {
  3.         Node tempNode = head;
  4.         Node newHead = new Node(0), tail = newHead;
  5.         Map<Node, Node> nodeMapping = new HashMap();
  7.         while (tempNode != null) {
  8.             Node node = new Node(tempNode.val);
  9.             tail.next = node;    // 尾插，保证顺序
  10.             tail = node;
  11.             nodeMapping.put(tempNode, node);
  12.             tempNode = tempNode.next;
  13.         }
  14.         tempNode = head;
  15.         while (tempNode != null) {
  16.             Node randomNode = tempNode.random;
  17.             nodeMapping.get(tempNode).random = nodeMapping.getOrDefault(randomNode, null);
  18.             tempNode = tempNode.next;
  19.         }
  20.         return newHead.next;
  21.     }
  22. }

时间复杂度为O(n)，空间复杂度为O(n)