图解LeetCode——138. 复制带随机指针的链表

一、题目

给你一个长度为 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;}
}