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

Leetcode138. 复制带随机指针的链表

news 2025/8/21 3:48:12

复制带随机指针的链表

第一步拷贝节点链接在原节点的后面
第二步拷贝原节点的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 ;}