复制带随机指针的链表（ LeetCode 138 ）
一、题目描述
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
提示：
-10000 <= Node.val <= 10000Node.random为空（null）或指向链表中的节点。- 节点数目不超过 1000 。
二、题目解析
对于链表中的每个节点来说，它都有三个特征：
- 值为 val
- 一个指向下一个节点的指针
next - 一个指向随机节点的指针
random
要想复制这样一个复杂链表必须要考虑到这三个特征。
如果没有 random 指针的话，那就是普通的链表，只需要遍历链表，然后每轮创建新节点，同时赋值 val 和调整前驱指针指向当前节点就行。
这题出现了 random 指针，由于它可以指向 null 、前面的节点或者后面的节点， 无法做到在一次遍历的过程中就确定下来，因为如果是指向后面的节点，但后面的节点还没有创建生成，无法确定。
所以，我们需要在一开始把所有的节点都创建出来，避免 random 找不到指向，同时观察上图，每个节点都通过 random 对应着一个新的节点，这种一一对应的关系，符合哈希表的特征。
此时的哈希表以原链表的节点作为键，新创建的节点作为值。
原链表（Key）中的每个节点都有 next 和 random 指针，而新链表（Value） 没有 next 和 random 指针。
需要通过第二次的遍历过程进行指针指向的调整。
在第二次遍历过程中，以原链表中的节点作为键，查找当前原节点的指针指向，然后调整新节点的指针指向。
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 复制带随机指针的链表（ LeetCode 138 ）:https://leetcode-cn.com/problems/copy-list-with-random-pointer
class Solution {
public Node copyRandomList(Node head) {
// 边界判断，一般链表的题目都需要判断头节点是否为空
if(head == null) return null;
// 从链表的头节点开始遍历
Node cur = head;
// 使用一一对应的哈希表结构 Map 存放已经创建的节点
Map<Node,Node> map = new HashMap<>();
// 遍历原链表
while( cur != null ) {
// 以原链表的节点为 Key，构建一个 Map
// Map 的 Value 为一个新链表中的节点
// 新节点的值 val 和原链表的值 val 一样
// 但原链表中的每个节点都有 next 和 random 指针，而 Map 中的 Value 没有 next 和 random 指针
// map.put(Key,Value)
map.put(cur,new Node(cur.val));
// 查看下一个节点的情况
cur = cur.next;
}
// 再次从链表的头节点开始遍历
cur = head;
// 遍历原链表
while( cur != null ) {
// 原链表节点 ---- 新链表节点
// key ----- value
// cur ----- map.get(cur)
// 0、在字典中找到一个 cur 为 key 对应的那个 value 值
Node valueCur = map.get(cur);
// 接下来，需要去寻找 valueCur 的 next 节点和 random 节点
// 寻找 valueCur 的 next 节点
// 1、获取当前节点 cur 在原链表中的 next 指针指向的节点
Node keyNextNode = cur.next;
// 2、在字典中找到以 keyNextNode 为 key 对应的那个 value 值
Node valueNextNode = map.get(keyNextNode);
// 3、那么新链表中的这个节点的 next 指针就是 valueNextNode
valueCur.next = valueNextNode;
// 寻找 valueCur 的 节点
// 1、获取当前节点 cur 在原链表中的 random 指针指向的节点
Node keyRandomNode = cur.random;
// 2、在字典中找到以 valueRandomNode 为 key 对应的那个 value 值
Node valueRandomNode = map.get(keyRandomNode);
// 4、那么新链表中的这个节点的 next 指针就是 valueNextNode
valueCur.random = valueRandomNode;
//遍历下去，查看下一个节点
cur = cur.next;
}
// 原链表节点 ---- 新链表节点
// key ----- value
// cur ----- map.get(cur)
// head ----- map.get(head)
return map.get(head);
}
}
2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 复制带随机指针的链表（ LeetCode 138 ）:https://leetcode-cn.com/problems/copy-list-with-random-pointer
class Solution {
public:
Node* copyRandomList(Node* head) {
// 边界判断，一般链表的题目都需要判断头节点是否为空
if(head == NULL) return NULL;
// 从链表的头节点开始遍历
Node* cur = head;
// 使用一一对应的哈希表结构 Map 存放已经创建的节点
unordered_map<Node*, Node*> map;
// 遍历原链表
while( cur != NULL ) {
// 以原链表的节点为 Key，构建一个 Map
// Map 的 Value 为一个新链表中的节点
// 新节点的值 val 和原链表的值 val 一样
// 但原链表中的每个节点都有 next 和 random 指针，而 Map 中的 Value 没有 next 和 random 指针
// map.put(Key,Value)
Node *newNode = new Node(cur->val);
map[cur] = newNode;
// 查看下一个节点的情况
cur = cur->next;
}
// 再次从链表的头节点开始遍历
cur = head;
// 遍历原链表
while( cur != NULL ) {
// 原链表节点 ---- 新链表节点
// key ----- value
// cur ----- map.[cur]
// 0、在字典中找到一个 cur 为 key 对应的那个 value 值
Node* valueCur = map[cur];
// 接下来，需要去寻找 valueCur 的 next 节点和 random 节点
// 寻找 valueCur 的 next 节点
// 1、获取当前节点 cur 在原链表中的 next 指针指向的节点
Node* keyNextNode = cur->next;
// 2、在字典中找到以 keyNextNode 为 key 对应的那个 value 值
Node* valueNextNode = map[keyNextNode];
// 3、那么新链表中的这个节点的 next 指针就是 valueNextNode
valueCur->next = valueNextNode;
// 寻找 valueCur 的 节点
// 1、获取当前节点 cur 在原链表中的 random 指针指向的节点
Node* keyRandomNode = cur->random;
// 2、在字典中找到以 valueRandomNode 为 key 对应的那个 value 值
Node* valueRandomNode = map[keyRandomNode];
// 4、那么新链表中的这个节点的 next 指针就是 valueNextNode
valueCur->random = valueRandomNode;
//遍历下去，查看下一个节点
cur = cur->next;
}
// 原链表节点 ---- 新链表节点
// key ----- value
// cur ----- map[cur]
// head ----- map[head]
return map[head];
}
};
3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 复制带随机指针的链表（ LeetCode 138 ）: https://leetcode-cn.com/problems/copy-list-with-random-pointer
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
# 边界判断，一般链表的题目都需要判断头节点是否为空
if head == None :
return None
# 从链表的头节点开始遍历
cur = head
# 使用一一对应的哈希表结构 Map 存放已经创建的节点
map = dict()
# 遍历原链表
while cur != None :
# 以原链表的节点为 Key，构建一个 Map
# Map 的 Value 为一个新链表中的节点
# 新节点的值 val 和原链表的值 val 一样
# 但原链表中的每个节点都有 next 和 random 指针，而 Map 中的 Value 没有 next 和 random 指针
new_node = Node(cur.val,None,None)
map[cur] = new_node
# 查看下一个节点的情况
cur = cur.next
# 再次从链表的头节点开始遍历
cur = head
# 遍历原链表
while cur != None :
# 原链表节点 ---- 新链表节点
# key ----- value
# cur ----- map.get(cur)
# 0、在字典中找到一个 cur 为 key 对应的那个 value 值
valueCur = map.get(cur)
# 接下来，需要去寻找 valueCur 的 next 节点和 random 节点
# 寻找 valueCur 的 next 节点
# 1、获取当前节点 cur 在原链表中的 next 指针指向的节点
keyNextNode = cur.next
# 2、在字典中找到以 keyNextNode 为 key 对应的那个 value 值
valueNextNode = map.get(keyNextNode)
# 3、那么新链表中的这个节点的 next 指针就是 valueNextNode
valueCur.next = valueNextNode
# 寻找 valueCur 的 节点
# 1、获取当前节点 cur 在原链表中的 random 指针指向的节点
keyRandomNode = cur.random
# 2、在字典中找到以 valueRandomNode 为 key 对应的那个 value 值
valueRandomNode = map.get(keyRandomNode)
# 4、那么新链表中的这个节点的 next 指针就是 valueNextNode
valueCur.random = valueRandomNode
#遍历下去，查看下一个节点
cur = cur.next
# 原链表节点 ---- 新链表节点
# key ----- value
# cur ----- map.get(cur)
# head ----- map.get(head)
return map.get(head)
