给出一个链表，每个节点包含一个额外增加的随机指针可以指向链表中的任何节点或空的节点。
返回一个深拷贝的链表。
思路
本题有点类似于克隆图的题目，可以用克隆图方法解，但需要花费 O(n) 额外空间，所以我们用局部变量解法
挑战
可否使用 O(1) 的空间
额外空间是指除了输入空间和输出空间之外的空间，局部变量是 O(1) 的额外空间可以忽略不计，即 constant memory
注：
最开始的思路是简单的想到了每遍历一个结点就复制一个结点，但是随机指针是连接任意一结点，这就出现可能会通过随机结点返回到之前结点，从而产生重复现象，所以要使用 hash 表去重
代码
- HashMap version
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) {
return null;
}
HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
RandomListNode dummy = new RandomListNode(0);
// 建立 pre 的目的就是要记录上一个结点位置，这样才能将新的结点连成一个链表
// 变量的初始化命名要在循环外，否则每次循环就会重新初始化变量值，这样变量就不会改变了
// dummy 是复制链表的头结点
RandomListNode pre = dummy;
RandomListNode newNode;
// 整个 while 循环每次 copy 一个结点的信息
while (head != null) {
// 建立新旧结点的映射关系
if (map.containsKey(head)) {
newNode = map.get(head);
} else {
newNode = new RandomListNode(head.label);
map.put(head, newNode);
}
// 上述代码复制一个新的结点，将新复制的结点连接成链表
pre.next = newNode;
// copy 随机指针的映射关系
// head.random为空时，则直接移到下一个结点
// 通过.random 来实现 head 结点和 random 结点的连接关系
if (head.random != null) {
// head.random 也是一个结点，每个结点对应着很多信息
if (map.containsKey(head.random)) {
newNode.random = map.get(head.random);
} else {
newNode.random = new RandomListNode(head.random.label);
map.put(head.random, newNode.random);
}
}
// copy 完映射关系就意味着这个结点全部操作完成
// 对于原来链表和复制链表都应该从当前结点移到下一个结点
// 之前 pre 在 newNode 的前一个结点
// 现在将 pre 移到 newNode 即 pre 后移一位
pre = newNode;
// head后移一位
head = head.next;
}
return dummy.next;
}
}
- No HashMap version
思路
第一遍扫的时候巧妙运用 next 指针， 开始数组是1->2->3->4
然后扫描过程中先建立 copy 节点1->1->2->2->3->3->4->4,
然后第二遍 copy 的时候去建立边的 copy，拆分结点，
一边扫描一边拆成两个链表，这里用到两个 dummy node。
第一个链表变回1->2->3, 然后第二变成1->2->3
public class Solution {
private void copyNext(RandomListNode head) {
while (head != null) {
RandomListNode newNode = new RandomListNode(head.label);
// 注意此处并不是copy random，而是 copy 结点信息，将 copy 完的新结点插入链表
newNode.random = head.random;
newNode.next = head.next;
head.next = newNode;
head = head.next.next;
}
}
private void copyRandom(RandomListNode head) {
while (head != null) {
// 只要 head.next.random 的指向是存在的,就需要将引用赋给它
if (head.next.random != null) {
head.next.random = head.random.next;
}
head = head.next.next;
}
}
private RandomListNode splitList(RandomListNode head) {
RandomListNode newHead = head.next;
while (head != null) {
RandomListNode temp = head.next;
head.next = temp.next;
head = head.next;
// 此处也可以写if (head != null)都是一个结点
if (temp.next != null) {
temp.next = temp.next.next;
}
}
return newHead;
}
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) {
return null;
}
copyNext(head);
copyRandom(head);
return splitList(head);
}
}
