前言
中间又断更新。
正文
问题来源
本问题来自leetcode上的138题。
问题描述
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的深拷贝。
示例 1:
输入：
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}
解释：
节点 1 的值是 1，它的下一个指针和随机指针都指向节点 2 。
节点 2 的值是 2，它的下一个指针指向 null，随机指针指向它自己。
分析：
用一个map来记录源节点地址和目标节点的地址，最后根据节点中存储的random指针，查询map中对应的目标节点的地址。
class Solution {
public:
Node* copyRandomList(Node* head) {
if (head == NULL) {
return NULL;
}
map<Node*,Node*> record;
Node *ret = new Node(head->val, NULL, head->random);
record.insert(pair<Node*,Node*>(head, ret));
Node *p = ret;
//if (head != NULL) {
head = head->next;
//}
while (head != NULL) {
p->next = new Node(head->val, NULL, head->random);
record.insert(pair<Node*,Node*>(head, p->next));
p = p->next;
head = head->next;
}
p = ret;
while (p != NULL) {
map<Node*,Node*>::iterator it = record.find(p->random);
if (it != record.end()) {
p->random = it->second;
} else {
p->random = NULL;
}
p = p->next;
}
return ret;
}
};
总结：
勤思考。
结语
不管怎么样好好加油。
