自建网站如何赚钱,网站关键词快排名,预测2025年网络营销的发展,金融网站建设内容一.题目要求
给你一个长度为 n 的链表#xff0c;每个节点包含一个额外增加的随机指针 random #xff0c;该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成#xff0c;其中每个新节点的值都设为其对应的原节点的值…一.题目要求
给你一个长度为 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 − 1 0 4 -10^4 −104 Node.val 1 0 4 10^4 104 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_mapNode*,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;}
};六.题目总结
重点就是建立Node*,Node* 的哈希表
