链接:138. 随机链表的复制 - 力扣（LeetCode）

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) 
{   //用cur记录head结点//创建新节点插入原链表中，是为了了防止结点数值重复，还要查询是//哪个结点，导致时间复杂度为O（n^2）struct Node*cur=head;while(cur){struct Node*copy=(struct Node*)malloc(sizeof(struct Node));copy->val=cur->val;copy->next=cur->next;cur->next=copy;cur=copy->next;}//设置copy结点中的random指针cur = head;while(cur){   struct Node*copy=cur->next;if(cur->random==NULL){copy->random = NULL;}else{copy->random=cur->random->next;}cur=copy->next;}//把拷贝结点取下来尾插为新链表,然后恢复原链表struct ListNode*copyhead=NULL,*copytail=NULL;cur=head;while(cur){struct Node*copy=cur->next;struct Node*next=copy->next;if(copytail == NULL){copyhead=copytail=copy;}else{copytail->next=copy;copytail=copytail->next;}//cur->next=next 这个是恢复链表cur->next=next;cur=next;}return copyhead;
}