题目描述
给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的 深拷贝。
我们用一个由 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。
算法1
常规的赋值链表值和next,我们不知道随机指针的匹配,
使用遍历查找记录原指针指向的节点的索引,然后再赋值节点依次遍历找到对应的节点,这么做时间花费太高。
可以使用哈希进行加速
代码如下
C++ 代码
/*
// 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:
unordered_map<Node*,Node*> mm;
Node* copyRandomList(Node* head) {
if(head == NULL) return NULL;
Node* ret = new Node(head->val);
Node* p = head->next;
Node* newH = ret;
mm[head] = ret;
while(p!= NULL){
newH->next = new Node(p->val);
mm[p] = newH->next;
p = p->next;
newH = newH->next;
}
p = head;
Node* retp = ret;
//遍历链表 核对随机链表
while(p != NULL){
retp->random = mm[p->random];
p=p->next; retp=retp->next;
}
return ret;
}
};