[138] 随机链表的复制

[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 作为传入参数。输入head [[7,null],[13,0],[11,4],[10,2],[1,0]]输出[[7,null],[13,0],[11,4],[10,2],[1,0]] 解题思路使用哈希表从 原链表新链表 映射解题。先从前到后遍历一遍构建新链表的val并且建立起原链表到新链表的映射。然后再遍历一遍根据原链表的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){Node*dummynewNode(0);Node*taildummy,*hhead;unordered_mapNode*,Node*randomList;while(h){tail-nextnewNode(h-val);tailtail-next;randomList[h]tail;hh-next;}taildummy-next;hhead;while(tail){tail-randomrandomList[h-random];tailtail-next;hh-next;}returndummy-next;}}; 复杂度分析时间复杂度O(n)空间复杂度O(n)日期2026-4-2