题目描述（中等难度）
给一个链表，返回复制后的链表。链表节点相对于普通的多了一个 random 指针，会随机指向链表内的任意节点或者指向 null。
思路分析
这道题其实和 133 题 复制一个图很类似，这里的话就是要解决的问题就是，当更新当前节点的 random 指针的时候，如果 random 指向的是很后边的节点，但此时后边的节点还没有生成，那么我们该如何处理。
和 133 题 一样，我们可以利用 HashMap 将节点提前生成并且保存起来，第二次遍历到他的时候直接从 HashMap 里边拿即可。
这里的话就有两种思路，一种需要遍历两边链表，一种只需要遍历一遍。
2020.3.3 更新，leetcode 增加了样例，之前没有重复的数字所以
key存的val，现在有了重复数字，将key修改为Node。此外Node的无参的构造函数也被去掉了，也需要修改。
解法一
首先利用 HashMap 来一个不用思考的代码。
遍历第一遍链表，我们不考虑链表之间的相互关系，仅仅生成所有节点，然后把它存到 HashMap 中，val 作为 key，Node 作为 value。
遍历第二遍链表，将之前生成的节点取出来，更新它们的 next 和 random 指针。
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
HashMap<Node, Node> map = new HashMap<>();
Node h = head;
while (h != null) {
Node t = new Node(h.val);
map.put(h, t);
h = h.next;
}
h = head;
while (h != null) {
if (h.next != null) {
map.get(h).next = map.get(h.next);
}
if (h.random != null) {
map.get(h).random = map.get(h.random);
}
h = h.next;
}
return map.get(head);
}
解法二
解法一虽然简单易懂，但还是有可以优化的地方的。我们可以只遍历一次链表。
核心思想就是延迟更新它的 next。
1 -> 2 -> 3
用 cur 指向已经生成的节点的末尾
1 -> 2
^
c
然后将 3 构造完成
最后将 2 的 next 指向 3
1 -> 2 -> 3
^
c
期间已经生成的节点存到 HashMap 中，第二次遇到的时候直接从 HashMap 中拿
看下代码理解一下含义吧
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
HashMap<Node, Node> map = new HashMap<>();
Node h = head;
Node cur = new Node(-1); //空结点，dummy 节点，为了方便头结点计算
while (h != null) {
//判断当前节点是否已经产生过
if (!map.containsKey(h)) {
Node t = new Node(h.val);
map.put(h, t);
}
//得到当前节点去更新它的 random 指针
Node next = map.get(h);
if (h.random != null) {
//判断当前节点是否已经产生过
if (!map.containsKey(h.random)) {
next.random = new Node(h.random.val);
map.put(h.random, next.random);
} else {
next.random = map.get(h.random);
}
}
//将当前生成的节点接到 cur 的后边
cur.next = next;
cur = cur.next;
h = h.next;
}
return map.get(head);
}
解法三
上边的两种解法都用到了 HashMap ，所以额外需要 O(n) 的空间复杂度。现在考虑不需要额外空间的方法。
主要参考了这里。主要解决的问题就是我们生成节点以后，当更新它的 random 的时候，怎么找到之前生成的节点，前两种解法用了 HashMap 全部存起来，这里的话可以利用原来的链表的指针域。
主要需要三步。
- 生成所有的节点，并且分别插入到原有节点的后边
- 更新插入节点的
random - 将新旧节点分离开来
一图胜千言，大家看一下下边的图吧。
代码对应如下。
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
Node l1 = head;
Node l2 = null;
//生成所有的节点，并且分别插入到原有节点的后边
while (l1 != null) {
l2 = new Node(l1.val);
l2.next = l1.next;
l1.next = l2;
l1 = l1.next.next;
}
//更新插入节点的 random
l1 = head;
while (l1 != null) {
if (l1.random != null) {
l1.next.random = l1.random.next;
}
l1 = l1.next.next;
}
l1 = head;
Node l2_head = l1.next;
//将新旧节点分离开来
while (l1 != null) {
l2 = l1.next;
l1.next = l2.next;
if (l2.next != null) {
l2.next = l2.next.next;
}
l1 = l1.next;
}
return l2_head;
}
解法四
不利用额外的空间复杂度还有一种思路，参考 这里。
解法三利用原链表的 next 域把新生成的节点保存了起来。类似的，我们还可以利用原链表的 random 域把新生成的节点保存起来。
主要还是三个步骤。
- 生成所有的节点，将它们保存到原链表的
random域，同时利用新生成的节点的next域保存原链表的random。 - 更新新生成节点的
random指针。 - 恢复原链表的
random指针，同时更新新生成节点的next指针。
一图胜千言。
相应的代码如下。
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
Node l1 = head;
Node l2 = null;
//生成所有的节点，讲它们保存到原链表的 random 域，
//同时利用新生成的节点的 next 域保存原链表的 random。
while (l1 != null) {
l2 = new Node(l1.val);
l2.next = l1.random;
l1.random = l2;
l1 = l1.next;
}
l1 = head;
//更新新生成节点的 random 指针。
while (l1 != null) {
l2 = l1.random;
l2.random = l2.next != null ? l2.next.random : null;
l1 = l1.next;
}
l1 = head;
Node l2_head = l1.random;
//恢复原链表的 random 指针，同时更新新生成节点的 next 指针。
while (l1 != null) {
l2 = l1.random;
l1.random = l2.next;
l2.next = l1.next != null ? l1.next.random : null;
l1 = l1.next;
}
return l2_head;
}
总
解法一、解法二是比较直接的想法，直接利用 HashMap 存储之前的节点。解法三、解法四利用原有链表的指针，通过指来指去完成了赋值。链表操作的核心思想就是，在改变某一个节点的指针域的时候，一定要把该节点的指针指向的节点用另一个指针保存起来，以免造成丢失。
更多详细通俗题解详见 leetcode.wang 。
