题目链接
题目简介
思路
先连要复制的点在原链表上，再把random正确链接，再解除与原链表的连接并还原原链表。
/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ struct Node* copyRandomList(struct Node* head) { if(head==NULL) return NULL; struct Node* cur=head; //把要复制的链表插入原链表 while(cur!=NULL) { struct Node* copy=(struct Node*)malloc(sizeof(struct Node)); if(copy==NULL) { printf("malloc fail\n"); exit(-1); } copy->next=cur->next; cur->next=copy; copy->val=cur->val; cur= cur->next->next; } //让newnode的random指向正确位置 cur=head; struct Node* copyhead=cur->next; struct Node* copy=cur->next; while(cur) { struct Node* copy=cur->next; if(cur->random == NULL) { copy->random=NULL; } else { copy->random=cur->random->next; } cur=copy->next; } //拷贝节点解下来，并链接到一起 cur=head; struct Node* copytail=NULL; copyhead=NULL; while(cur) { struct Node* copy=cur->next; struct Node* next=copy->next; cur->next=next; if(copytail==NULL)//尾插 { copyhead=copytail=copy; } else { copytail->next=copy; copytail=copytail->next; } cur=next; } return copyhead; }
最后的最后，创作不易，希望读者三连支持💖
赠人玫瑰，手有余香💖
