门户网站系统建设招标文件,python 做的网站有哪些,浙江电商网络推广,暂时关闭wordpress复制带随机指针的链表 第一步 拷贝节点链接在原节点的后面 第二步拷贝原节点的random #xff0c; 拷贝节点的 random 在原节点 random 的 next 第三步 将拷贝的节点尾插到一个新链表 ,并且将原链表恢复 从前往后遍历链表 ,将原链表的每个节点进行复制#xff0c;并l链接到原…复制带随机指针的链表 第一步 拷贝节点链接在原节点的后面 第二步拷贝原节点的random 拷贝节点的 random 在原节点 random 的 next 第三步 将拷贝的节点尾插到一个新链表 ,并且将原链表恢复 从前往后遍历链表 ,将原链表的每个节点进行复制并l链接到原节点的后面 malloc 一个节点copy cur 往后走 ,不能写成cur cur-next ,因为已经改变了链接关系,找不到cur的下一个节点的地址了 第一步的代码
struct Node* copyRandomList(struct Node* head){struct Node * cur head ;//cur 走到NULL 结束 while(cur){struct Node * copy ( struct Node *)malloc ( sizeof( stuct Node)); //拷贝copy-val cur-val;struct Node * next cur-next ;// 改变链接关系 cur copy next cur-next copy ;copy-next next ;//cur 往后走 ,不能写成cur cur-next ,因为已经改变了链接关系,找不到cur的下一个节点的地址了 cur next ;}
}对原链表 random 指针的复刻 , 即原节点 的 random 拷贝到 拷贝节点 的 random 里面 原节点 13的random指针指向原节点 7 ,拷贝的新节点 13的random指针也需要指向拷贝的节点7 如果原节点的random指针指向NULL ,新拷贝的节点的random指针也指向NULL 第二步的代码
//处理拷贝节点的random while(cur){struct Node * copy cur-next ;if(cur-random NULL){copy-random NULL ;//如果原节点的random指针指向NULL ,新拷贝的节点的random指针也指向NULL}else {copy-random cur-random-next ;// 对原链表 random 指针的复刻}cur cur-next-next ;}上图中我们可以观察到原节点 13的random指针指向原节点 7拷贝的新节点13的random指针指向的是原节点7的next 推广一下也就是说 原节点 i 的random指针指向的是原节点 j 那么新拷贝的节点 的random指针,指向的是原节点 j 的 next 但是这样下来 已经破坏了原链表 所以下一步是将拷贝的节点尾插到一个新链表 ,并且将原链表恢复 尾插
恢复原链表 第三步代码 //将拷贝的新节点尾插到一个新链表, 并恢复原链表cur head ;struct Node * copyhead NULL , * copyTail NULL ;while( cur){ struct Node * copy cur-next ;struct Node * next copy-next ; //尾插if( copyhead NULL){copyhead copyTail copy ;}else{copyTail-next copy ;copyTail copyTail-next ;}//恢复原链表cur-next next ;cur next ;}
完整代码
struct Node* copyRandomList(struct Node* head){struct Node * cur head ;//cur 走到NULL 结束 while(cur){struct Node * copy ( struct Node *)malloc ( sizeof( struct Node)); //拷贝copy-val cur-val;struct Node * next cur-next ;// 改变链接关系 cur copy next cur-next copy ;copy-next next ;//cur 往后走 ,不能写成cur cur-next ,因为已经改变了链接关系,找不到cur的下一个节点的地址了 cur next ;}cur head ;//处理拷贝节点的random while(cur){struct Node * copy cur-next ;if(cur-random NULL){copy-random NULL ;}else {copy-random cur-random-next ;//}cur cur-next-next ;}//将拷贝的新节点尾插到一个新链表, 并恢复原链表cur head ;struct Node * copyhead NULL , * copyTail NULL ;while( cur){ struct Node * copy cur-next ;struct Node * next copy-next ; //尾插if( copyhead NULL){copyhead copyTail copy ;}else{copyTail-next copy ;copyTail copyTail-next ;}//恢复原链表cur-next next ;cur next ;}return copyhead ;}如果你觉得这篇文章对你有帮助不妨动动手指给点赞收藏加转发给鄃鳕一个大大的关注 你们的每一次支持都将转化为我前进的动力
