【LeetCode热题100】138. 随机链表的复制（链表）

一.题目要求

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random -> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random -> y 。返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到
n-1）；如果不指向任何节点，则为 null 。

你的代码只接受原链表的头节点 head 作为传入参数。

二.题目难度

中等

三.输入样例

示例 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]]

提示：
0 <= n <= 1000
$10^4$ <= Node.val <= $10^4$
Node.random 为 null 或指向链表中的节点。

四.解题思路

1.遍历一次，新建一个与原来链表val和next相同的链表，将原链表和新链表一一对应的元素地址做成哈希映射。
2.再次遍历，新表中random指向原表中根据原表random在哈希表中对应的新表的random。

五.代码实现

/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;}
};
*//*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;}
};
*/class Solution {
public:Node* copyRandomList(Node* head) {unordered_map<Node*,Node*> nodeMap;Node* dummy = new Node(-1);Node* back = dummy;Node* p = head;while(p){back->next = new Node(p->val);back = back->next;nodeMap.insert(make_pair(p, back));p = p->next;}back = dummy->next;while(head){back->random = nodeMap[head->random];head = head->next;back = back->next;}return dummy->next;}
};