/*** Definition for a Node.* struct Node {* int val;* struct Node *next;* struct Node *random;* };*/typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) {if(head==NULL)return NULL;//1.拷贝结点，连接到原结点的后面Node*cur=head;while(cur){Node*copy=(Node*)malloc(sizeof(Node));copy->next=NULL;copy->random=NULL;copy->val=cur->val;// //相当于插入// copy->next=cur->next;// cur->next=copy;Node*next=cur->next;cur->next=copy;copy->next=next;cur=next;}//2.处理拷贝结点的randomcur=head;while(cur){Node*copy=cur->next;if(cur->random)copy->random=cur->random->next;elsecopy->random=NULL;cur=cur->next->next;}//3.拆cur=head;Node*copyHead=head->next;//因为函数最后返回的是头指针while(cur){Node*copy=cur->next;Node*next=cur->next->next;cur->next=next;if(next)copy->next=next->next;elsecopy->next=NULL;cur=next;}return copyHead;
}
