惠州网站建设服务商,进入秦皇岛最新规定,和田哪里有做网站的地方,广州最新重大新闻题目描述#xff1a;
给你一个长度为 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 作为传入参数。
图示 输入head [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出[[7,null],[13,0],[11,4],[10,2],[1,0] 目录
1.解题思路
1.1思路1
1.2思路2
2.软件编程
2.1拷贝节点链接进原节点
2.2处理random节点 2.3深度拷贝 1.解题思路
1.1思路1
第一步首先通过便利的方法将每个节点拷贝一份且next指针明确。如下图示 第二步处理random指针 首先需要明确的是我们是对原链表进行的拷贝新链表和原链表已经没有联系我们不可以通过原链表的指针去寻找random指向更不可能通过数值去寻找random指向如果有相同值得节点random该指向谁呢如下图所示 所以靠数值寻找random指向是不合理的会出现重复值得情况导致指向出问题。
第三步我们通过相对位置去寻找random指向譬如头结点是位置0依次是1、2、3、等当我们寻找13指向就是相对头结点偏移零个位置11的random指向就是相对头结点 偏移4个位置。
这个方法虽然能实现深层拷贝但是时间复杂度是O()。
1.2思路2 第一步在原链表的基础上新增跟原链表相同的节点并插入到对应数值得节点之后
如下图所示 第二步处理random节点当我们复制新的节点在对应节点之后新节点的random 就是原节点random 的拷贝也就是next图示如下 第三步: 深度拷贝
我们需要将拷贝好的节点取下来重新next指向完成深度拷贝然后恢复原节点指向图解如下 2.软件编程
2.1拷贝节点链接进原节点
struct Node* copyRandomList(struct Node* head) {//插入拷贝的节点链接进原链表struct Node* cur head;//定义遍历节点while(cur){struct Node* copy (struct Node *)malloc(sizeof(struct Node));//复制节点堆上申请struct Node* next cur-next;//记录下一个节点指向if(copy NULL){perror(malloc:fail);exit(-1);}copy-val cur-val;cur-next copy;copy-next next;cur next;}
2.2处理random节点 //处理随机节点指向cur head;while(cur){struct Node* copy cur-next;if(cur-random NULL){copy-random NULL;}else{copy-random cur-random-next;}cur copy-next;} 2.3深度拷贝 //深度拷贝struct Node*copyhead NULL,*copytail NULL;cur head;while(cur){struct Node *copy cur-next;struct Node *next copy-next;if(copyhead NULL){copyhead copytail cur-next;}else{copytail-next copy;copytail copytail-next;}cur-next next;cur next;}return copyhead;
