LeetCode138. 随机链表的复制（2024秋季每日一题 34）

给你一个长度为 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]]0n10000 n 10000n1000−104Node.val104-10^4 Node.val 10^4−104Node.val104Node.random 为 null 或指向链表中的节点。推荐解法二的写法快解法一思路用 hash 表记录原链表中每个节点对应的下标通过 hash 表将每个节点对应的 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; } }; */classSolution{public:Node*copyRandomList(Node*head){unordered_mapNode*,intmp;intn0;Node*curhead;while(cur!NULL){mp[cur]n;curcur-next;n;}vectorintrd(n);curhead;for(inti0;in;i){if(mp.count(cur-random)){rd[i]mp[cur-random];}else{rd[i]-1;}curcur-next;}curhead;Node*hnewNode(0);Node*preh;vectorNode*ls;while(cur!NULL){Node*tnewNode(cur-val);ls.push_back(t);pre-nextt;pret;curcur-next;}curh-next;for(inti0;in;i){if(rd[i]-1){cur-randomNULL;}else{cur-randomls[rd[i]];}curcur-next;}returnh-next;}};/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val _val; next NULL; random NULL; } }; */classSolution{public:Node*copyRandomList(Node*head){Node*h1head;unordered_mapNode*,intnodeMap;vectorNode*v1,v2;Node*newHeadnullptr,*newHnullptr;for(inti0;h1!nullptr;i,h1h1-next){v1.push_back(h1);nodeMap[h1]i;if(newHeadnullptr){newHeadnewNode(h1-val);newHnewHead;}else{newH-nextnewNode(h1-val);newHnewH-next;}v2.push_back(newH);}h1head;newHnewHead;for(inti0;h1!nullptrnewH!nullptr;i){Node*rh1-random;if(r!nullptr){intidxnodeMap[r];newH-randomv2[idx];}h1h1-next;newHnewH-next;}returnnewHead;}};解法二缓存每一个 旧节点 - 新节点的映射对于当前旧节点如果在缓存中存在则直接返回对应的新节点如果当前旧节点在缓存中不存在则创建对应新节点、接入映射缓存中并对于当前 next 和 random 指针找到其在缓存中的映射复制给对应指针通过方法获取【有点像 记忆化dp】classSolution{public:unordered_mapNode*,Node*mp;Node*copyRandomList(Node*head){if(headNULL)returnNULL;if(!mp.count(head)){Node*nodenewNode(head-val);mp[head]node;node-nextcopyRandomList(head-next);node-randomcopyRandomList(head-random);}returnmp[head];}};解法三遍历每个旧节点创建对应新节点并将其插入当前节点后面 (newNode - next node - next;node - next newNode;)一条链遍历所有旧/新节点新节点 random 指针 指向对应 旧节点 random 指针的 next 位置的节点也是这个random旧节点对应的新节点遍历旧/新节点将旧/新节点分别拆成两条链返回新节点的头指针/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val _val; next NULL; random NULL; } }; */classSolution{public:Node*copyRandomList(Node*head){if(headNULL){returnNULL;}Node*curhead;// 插入while(cur!NULL){Node*nodenewNode(cur-val);node-nextcur-next;cur-nextnode;curcur-next-next;}// update复制链表的random指针curhead;while(cur!NULL){if(cur-random!NULL){cur-next-randomcur-random-next;}curcur-next-next;}// update next指针Node*cPrenewNode(0);curhead;Node*rescPre;while(cur!NULL){cPre-nextcur-next;cur-nextcur-next-next;curcur-next;cPrecPre-next;}// 返回头指针returnres-next;}};