本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
本题来自 LeetCode：138. 复制带随机指针的链表[1]
题目描述
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的 深拷贝。
我们用一个由
n个节点组成的链表来表示输入/输出中的链表。每个节点用一个
[val, random_index]表示：
val：一个表示
Node.val的整数。
random_index：随机指针指向的节点索引（范围从
0到
n-1）；如果不指向任何节点，则为
null。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
示例 4：
输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。
提示：
-10000 = Node.val = 10000
Node.random 为空（
null）或指向链表中的节点。
节点数目不超过
1000。
解法一
题目分析
本题题意是复制一个带随机指针的链表，主要处理的难点在随机指针的不确定性。可以先利用额外的空间，来存储
老节点和
新节点映射关系。
题目解答
/*
// 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;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
MapNode, Node table = new HashMap();
Node currentNode = head;
// 新链表头节点
Node copyHead = null;
Node copyCurrentNode = null;
// 1. 创建新链表，设置每个节点val和next字段
while(currentNode != null) {
// 设置val
Node node = new Node(currentNode.val);
// 新链表头节点
if(copyHead == null) {
copyHead = node;
copyCurrentNode = node;
} else {
// 设置next字段
copyCurrentNode.next = node;
copyCurrentNode = copyCurrentNode.next;
}
// 保存映射关系
table.put(currentNode, node);
currentNode = currentNode.next;
}
currentNode = head;
// 2. 设置新链表每个字段的random字段
while(currentNode != null) {
if(currentNode.random != null) {
table.get(currentNode).random = table.get(currentNode.random);
}
currentNode = currentNode.next;
}
return copyHead;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(n)
解法二
题目分析
解法一我们使用了额外空间，额外空间主要用来映射新老节点的关系，如果我们能够采用某种方式找到个某个老节点对应的新节点，那就不需要额外来存储映射关系了。
我们在在每次创建新节点后，直接连接到老节点后面。这样通过随机指针来查找的时候，就可能很方便的找到相应的新节点了。比如：
原链表: A -- B -- C -- D
处理后的链表: A -- A' -- B -- B' -- C -- C' -- D -- D'
如果我们需要查找原节点B对应的新节点，直接取 B.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;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
if(head == null) {
return null;
}
Node currentNode = head;
// 1. 复制老链表的节点，让老节点和新节点交替连接，这一步可以设置新节点的val字段
while(currentNode != null) {
Node temp = currentNode.next;
// 设置val
Node node = new Node(currentNode.val);
currentNode.next = node;
node.next = temp;
currentNode = temp;
}
// 2. 根据交替链表，设置新节点的random字段
currentNode = head;
while(currentNode != null && currentNode.next != null) {
if(currentNode.random != null) {
currentNode.next.random = currentNode.random.next;
}
currentNode = currentNode.next.next;
}
// 新链表头节点
Node copyHead = null;
Node copyCurrentNode = null;
currentNode = head;
// 3. 设置新节点的next字段
while(currentNode != null && currentNode.next != null) {
if(copyHead == null) {
copyHead = currentNode.next;
copyCurrentNode = currentNode.next;
} else {
copyCurrentNode.next = currentNode.next;
copyCurrentNode = copyCurrentNode.next;
}
// 不能破坏原链表，要将原链表复原
currentNode.next = currentNode.next.next;
currentNode = currentNode.next;
}
return copyHead;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
解法三（不通过）
一开始我是用这种解法来解答的，不需要额外空间。但是由于修改了原链表，报以下错误。
Random pointer of node with label 7 from the original list was modified.
由于最终无法复原原链表，故该解法不通过，仅供参考。
解法的核心思想和
解法二类似，不同的是：
class Solution {
public Node copyRandomList(Node head) {
Node currentNode = head;
// 新链表头节点
Node copyHead = null;
Node copyCurrentNode = null;
// 1. 创建新链表，设置每个节点val和next字段
while(currentNode != null) {
// 设置val
Node node = new Node(currentNode.val);
// 新链表头节点
if(copyHead == null) {
copyHead = node;
copyCurrentNode = node;
} else {
// 设置next字段
copyCurrentNode.next = node;
copyCurrentNode = copyCurrentNode.next;
}
// 将新节点的random字段设置为老节点的random字段
copyCurrentNode.random = currentNode.random;
// 将老节点的random字段设置为老节点对应的新节点
currentNode.random = copyCurrentNode;
currentNode = currentNode.next;
}
copyCurrentNode = copyHead;
while(copyCurrentNode != null) {
Node temp = copyCurrentNode.random;
if(copyCurrentNode.random != null) {
copyCurrentNode.random = copyCurrentNode.random.random;
}
copyCurrentNode = copyCurrentNode.next;
}
return copyHead;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
参考资料
原文始发于微信公众号（xiaogan的技术博客）：
