网站服务器过期了怎么办,文交所网站开发,wordpress如何控制内容图片大小,手机主页网站哪个好用给你一个长度为 n 的链表#xff0c;每个节点包含一个额外增加的随机指针 random #xff0c;该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成#xff0c;其中每个新节点的值都设为其对应的原节点的值。新节点的 n…给你一个长度为 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 作为传入参数。
思路一回溯
c语言解法
struct Node* copyRandomList(struct Node* head) {struct Node* curhead;while(cur){struct Node* nextcur-next;struct Node* copy(struct Node*)malloc(sizeof(struct Node));copy-valcur-val;cur-nextcopy;copy-nextnext;curnext;}curhead;while(cur){struct Node* copycur-next;if(cur-randomNULL){copy-randomNULL;}else{copy-randomcur-random-next;}curcopy-next;}curhead;struct Node* copyheadNULL,*copytailNULL;while(cur){struct Node* copycur-next;struct Node* nextcopy-next;if(copytailNULL){copytailcopyheadcopy;}else{copytail-nextcopy;copytailcopytail-next;}cur-nextnext;curnext;}return copyhead;}
分析
本题要对一个特殊的链表进行复制这个链表每个节点包含一个额外增加的随机指针 random可以先将该链表每个节点记录下来当记录的节点的指针指向空节点时原复制的节点也指向空最后将操作完的链表用copytail连接起来最后输出copyhead
总结
本题考察对链表的操作要将链表深拷贝即将链表复制下来再根据具体情况添加最后连接后返回
