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

LeetCode-随机链表的复制

news 来源：原创 2024/9/19 8:15:31

. - 力扣（LeetCode）

本题思路：

首先注意到随机链表含有random的指针，这个random指针指向是随机的；先一个一个节点的拷贝，并且把拷贝的节点放在拷贝对象的后面，再让拷贝节点的next指向原链表拷贝对象的下一个节点，这样做的目的是实现拷贝节点的插入，即拷贝好的节点都放在原链表两个节点之间；

实现完拷贝节点的插入是为了实现拷贝节点random的指向；如果原链表拷贝对象的random指向为NULL，那么拷贝节点的random指向也置为NULL；若是拷贝对象的random指向不为NULL，那么就让拷贝节点的random指向拷贝对象的random的next，解释为什么要这样：假设现在要实现这个链表中一个拷贝节点的random指向，已知其他拷贝对象的next指向的就是拷贝节点；要实现random指向的这一个节点要找到和它拷贝对象一样的random指向，如何找到？只需要让这个拷贝节点的random指向它自己拷贝对象的random的next，这个被指向的拷贝节点就是原链表中这个要实现random指向的拷贝节点的拷贝对象的的random的next指向的拷贝节点；

最后再进行尾插操作，让拷贝节点形成一条新的链表；并且还原原链表；

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/
typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) {Node* cur=head;Node* next=NULL;Node* copy=NULL;while(cur){next=cur->next;copy=(Node*)malloc(sizeof(Node));copy->next=next;copy->val=cur->val;cur->next=copy;cur=next;}//拷贝节点的插入cur=head;while(cur){copy=cur->next;next=copy->next;if(cur->random==NULL){copy->random=NULL;}else{copy->random=cur->random->next;}cur=next;}拷贝节点random的指向实现cur=head;Node* copyhead,*copytail;copyhead=copytail=(Node*)malloc(sizeof(Node));copyhead->val=-1;copyhead->next=copyhead->random=NULL;while(cur){copy=cur->next;next=copy->next;copytail->next=copy;copytail=copytail->next;cur->next=next;cur=next;}//拷贝节点尾插变成新的要求的链表；还原成原链表Node* rsl=copyhead->next;free(copyhead);copyhead=NULL;return rsl;}