当前位置：首页 > news >正文

中国住房和城乡建设部网站安全软文自助发稿平台

news 2025/8/2 14:00:25

中国住房和城乡建设部网站安全,软文自助发稿平台,个人博客主页登录,咨询公司名字大全复制带随机指针的链表第一步拷贝节点链接在原节点的后面第二步拷贝原节点的random ， 拷贝节点的 random 在原节点 random 的 next 第三步将拷贝的节点尾插到一个新链表 ,并且将原链表恢复从前往后遍历链表 ,将原链表的每个节点进行复制，并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 ;}