必应网站建设,网站需要证件,建站网页模板,调查问卷wordpress复制带随机指针的链表1.题目2.解题思路3.完整代码1.题目
题目链接: https://leetcode.cn/problems/copy-list-with-random-pointer/
给你一个长度为 n 的链表#xff0c;每个节点包含一个额外增加的随机指针 random #xff0c;该指针可以指向链表中的任何节点或空节点。
…
复制带随机指针的链表1.题目2.解题思路3.完整代码1.题目
题目链接: https://leetcode.cn/problems/copy-list-with-random-pointer/
给你一个长度为 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 作为传入参数。
2.解题思路
我们分3个步骤来解决这个题目
1.复制结点插入到原结点和下一个结点之间
2.根据原结点的random处理复制结点的random
3.把拷贝的结点解下来存放到新的链表中恢复原链表的链接关系。
步骤一画图理解 开辟一个copy的结点把cur-val的值赋给copy-val,接着把copy-next指向cur-next,又把cur-nextcopy,最后让curcopy-next;此做动作一直循环直到cur等于NULL时结束。 步骤二 让copy指向cur的下一个结点,如果cur-randomNULL则copy-randomNULL否则copy-randomcur-random-next 最后curcopy-next此动作一直循环直到curNULL时结束。 第一个原结点的random指向的是NULL所以拷贝结点的random也是指向的NULL 第二个原结点的random指向的是7所以拷贝结点的random也是指向的7这里的7是拷贝结点的7 这里copy-randomcur-random-next不太好理解就是拷贝结点的random是指向原结点的random的next,这样才能指向7这个拷贝的结点。
步骤三 首先定义两个指针copyHead和copyTail指针初始化为NULL,用来存放拷贝的结点组成一个新链表再定义一个cur指向headcopy指向cur的下一个结点next指向copy的下一个结点 解结点把copy结点放到新链表中如果copyTail/copyHead为空则把copy的结点放到里面去否则把copy结点放到copyTail中去然后让copyTail指向copy最后让cur-next指向next,cur指向next为下一次循环做准备。 把拷贝的结点解下来的同时需要把原链表的链接关系重新链接好。
这样就算是把原链表深拷贝了。
3.完整代码
struct Node* copyRandomList(struct Node* head) {//复制结点插入到原结点和下一个结点之间struct Node* cur head;while(cur){struct Node* copy (struct Node*)malloc(sizeof(struct Node));copy-val cur-val;copy-next cur-next;cur-next copy;cur copy-next;}//根据原结点的random处理复制结点的randomcur head;while(cur) {struct Node* copy cur-next;if(cur-random NULL){copy-random NULL;}else{copy-random cur-random-next;}cur copy-next;}//把拷贝的结点解下来存放到新的链表中恢复原链表的链接关系struct Node* copyHead NULL, *copyTail NULL;cur head;while(cur){struct Node* copy cur-next;struct Node* next copy-next;if(copyTail NULL){copyHead copyTail copy;}else{copyTail-next copy;copyTail copy;}//为下一次循环做准备cur-next next;cur next;}return copyHead;
}不管你认为这篇文章写的好不好反正没人点赞
