共计 3270 个字符，预计需要花费 9 分钟才能阅读完成。
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的 深拷贝。
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
示例：
输入：{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}
解释：节点 1 的值是 1，它的下一个指针和随机指针都指向节点 2。节点 2 的值是 2，它的下一个指针指向 null，随机指针指向它自己。提示：
- 你必须返回 给定头的拷贝 作为对克隆列表的引用。
Note:
- You must return the copy of the given head as a reference to the cloned list.
解题思路：
由于需要考虑随机指针，随机指针指向的节点可能是 null，也可能是链表的最后一个节点，深拷贝下，你不能将新链表的随机指针指向原链表的节点，所以无法一遍得到新链表。
两种解题方法，一种是拷贝所有节点，暂存在一种数据结构内，然后再遍历一遍该数据结构，找到拷贝的节点，确定随机指针的指向。因为每个节点都要找到随机指针指向的节点，如果借助 散列表(字典) 其查找复杂度为 O(1)，这样可以把总时间复杂度降到 O(n)，由于要暂存所有节点，其空间复杂度为 O(n)。
另一种解题方法是需要三次遍历得到结果，简单来说就是先把每个节点拷贝，并把拷贝节点连接到原节点后面，依次类推。确定随机节点的关系之后再拆分链表。是一种很巧妙的思路：
原链表：1->2->3
复制每个节点到原节点后面：1->1->2->2->3->3
复制随机指针的指向关系
拆分链表：1->2->3, 1->2->3
复制随机指针指向时，原节点的随机节点下一个节点即为新节点的随机节点。假如原链表：1->2->3，节点 1 的随机节点为 3，复制节点之后：1->1->2->2->3->3
我们只需将 新节点 （原节点 1 的后一个节点 1）指向 原节点的随机节点的后一个节点（原节点的随机节点为 3，而复制之后随机节点 3 的后一个节点依然为 3，但这个节点为新节点），最后拆分链表（链表拆分不影响节点指向关系）。其时间复杂度为 O(n)，空间复杂度为 O(1)。
第一种方法：
Java：
class Solution {public Node copyRandomList(Node head) {if (head == null) return null;
HashMap<Node, Node> map = new HashMap<>();// 借助 hashMap
Node newHead = new Node(0);// 虚拟头节点
Node cur = newHead;// 指针指向当前节点
Node tmp;
while (head != null) {if (map.containsKey(head)) {// 查询原节点是否已存在于 map
tmp = map.get(head);// 如果存在直接取 value 值
} else {tmp = new Node(head.val);// 不存在则新建一个值相同的节点
map.put(head, tmp);// 存入 map，key 为原节点，value 为新节点
}
cur.next = tmp;
if (head.random != null) {// 原节点的随机节点不为空的情况下
if (map.containsKey(head.random)) {// 查询该随即节点是否已存在于 map
tmp.random = map.get(head.random);// 存在则直接将新节点的随机指针指向其 value 值
} else {tmp.random = new Node(head.random.val);// 不存在则新建一个值相同的随机节点
map.put(head.random, tmp.random);// 存入 map，key 为原节点的随机节点，value 为新节点的随机节点
}
}
head = head.next;// 刷新原链表当前头节点
cur = tmp;// 即 cur=cur.next，刷新新链表当前节点
}
return newHead.next;
}
}Python3：
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head: return None
map = {}
newHead = Node(val=0, next=None, random=None)
cur = newHead
while head:
if head in map.keys():
tmp = map.get(head)
else:
tmp = Node(val=head.val, next=None, random=None)
map.setdefault(head, tmp)
cur.next = tmp
if head.random:
if head.random in map.keys():
tmp.random = map.get(head.random)
else:
tmp.random = Node(val=head.random.val, next=None, random=None)
map.setdefault(head.random, tmp.random)
head = head.next
cur = tmp
return newHead.next第二种方法：
Java：
class Solution {public Node copyRandomList(Node head) {if (head == null) return null;
// 复制节点 1->2->3 ==> 1->1->1->2->2->3->3
Node cur = head;
while (cur != null) {
Node next = cur.next;
Node tmp = new Node(cur.val);
cur.next = tmp;
tmp.next = next;
cur = next;
}
// 复制随机指针
cur = head;
while (cur != null) {
//cur.next.random=> 新节点的随机节点 cur.random.next=> 原节点的随机节点的下一个节点
cur.next.random = cur.random == null ? null : cur.random.next;
cur = cur.next.next;// 链表扩展一倍后肯定是偶数位链表，所以可以直接用 cur.next.next
}
// 分离节点
cur = head;
Node newHead = head.next;// 新链表头节点
while (cur != null) {
Node tmp = cur.next;
cur.next = tmp.next;
cur = cur.next;
tmp.next = cur == null ? null : cur.next;
}
return newHead;
}
}Python3：
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head: return None
cur = head
while cur:
next = cur.next
tmp = Node(val=cur.val, next=next, random=None)
cur.next = tmp
cur = next
cur = head
while cur:
cur.next.random = cur.random.next if cur.random else None
cur = cur.next.next
cur = head
newHead = head.next
while cur:
tmp = cur.next
cur.next = tmp.next
cur = cur.next
tmp.next = cur.next if cur else None
return newHead欢迎关注微. 信公. 众号一起学习：爱写 Bug
