一、题目
给你一个长度为 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 作为传入参数。
二、示例
2.1> 示例 1：
【输入】head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
【输出】[[7,null],[13,0],[11,4],[10,2],[1,0]]
2.2> 示例 2：
【输入】head = [[1,1],[2,1]]
【输出】[[1,1],[2,1]]
2.3> 示例 3：
【输入】head = [[3,null],[3,0],[3,null]]
【输出】[[3,null],[3,0],[3,null]]
提示：
-
0<= n <=1000 -
-10^4<= Node.val <=10^4 -
Node.random为null或指向链表中的节点。
三、解题思路
3.1> 思路1：利用哈希表
根据题目描述，如果仅仅是单向链表，我们可以非常方便的通过在遍历旧的链表的同时来构建新的链表，但是本题中的一个难点是，存在一个属性是Node random，它用来表示随机的一个指针，执行链表中的任意节点，甚至是空节点。所以，针对这种特性，我们比较容易想到的一个解题思路就是借用哈希表来实现解题，其中：
【key】保存旧的链表节点；
【value】保存新建的链表节点；
这样，我们就可以通过两次遍历旧的链表来解答这道题的，逻辑如下所示：
【第1次遍历旧链表】将遍历的旧节点保存到
key中，将新建的节点保存到value中；
【第2次遍历旧链表】通过遍历旧节点的random节点寻找新建的random节点，并赋值给新的节点中；
以上就是解题思路，因为逻辑比较容易理解，所以此处就不画图了。
3.2> 思路2：原链表新建节点
除了上面利用哈希表的解题方式之外，我们其实可以不借助额外的容器来解题的。那么，在思路2中，我们就是采用在原有链表修改的方式进行解题的。为了便于描述，我们会以下面的链表为例：
本解题思路一共有如下3个步骤：
【步骤1】遍历旧的链表，每当遍历一个旧节点时，就在该节点的后面复制一个全新的节点，但是此时新节点中
random是没有值的；
【步骤2】再次遍历旧的链表，由于相同新旧两个节点是相邻的，所以我们可以得出一个规律，即：旧节点的random节点一定与新节点的random节点相邻。所以，我们以Node(3)为例，新的Node(3)的random就是旧的Node(3).random.next；
【步骤3】我们拆分新旧链表，这样，返回新链表的头节点即可；
如上就是思路2的解题思路了，为了方便大家理解，我们下面还是以图解的方式演示一下这3个步骤的操作方式。请见下图所示：
四、代码实现
4.1> 实现1：利用哈希表
class Solution {
public Node copyRandomList(Node head) {
if (head == null) return head;
Map<Node, Node> map = new HashMap();
Node p1 = head, temp = new Node(-1), p2 = temp;
while (p1 != null) {
map.put(p1, new Node(p1.val));
p1 = p1.next;
}
p1 = head;
while (p1 != null) {
Node node = map.get(p1);
node.random = map.get(p1.random);
p2.next = node;
p1 = p1.next;
p2 = p2.next;
}
return temp.next;
}
}
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
4.2> 实现2：原链表新建节点
class Solution {
public Node copyRandomList(Node head) {
if (head == null) return head;
Node temp = null, node = null;
// 步骤1：复制新节点
Node p1 = head;
while (p1 != null) {
temp = p1.next;
node = new Node(p1.val);
p1.next = node;
node.next = temp;
p1 = temp;
}
// 步骤2：关联random指针
Node p2 = head;
while (p2 != null) {
p2.next.random = (p2.random == null) ? null : p2.random.next;
p2 = p2.next.next;
}
// 步骤3：拆分出新的链表
Node nhead = new Node(-1), p3 = head, p4 = nhead;
while(p3 != null) {
p4.next = p3.next;
p4 = p3.next;
p3.next = p3.next.next;
p3 = p3.next;
}
return nhead.next;
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
