一、题目
给你一个长度为 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^4Node.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^)/ ~ 「干货分享，每天更新」
