单链表——随机链表的复制

本文主要是介绍单链表——随机链表的复制，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

深拷贝，就是将原链表彻底的拷贝，当我们观察这个链表时我们会发现，val与next都比较好拷贝，难点就是在random的拷贝，因为我们需要知被拷贝的节点的random指向的是哪个，所以我们很容易想到的方法就是从头遍历链表，再挨个进行拷贝，但是这样的话，我们的代码实现的时间复杂度为O(N^2)，效率低下，所以我们不采用这个方法。

第二种方法就是，我们可以在原链表中的每个节点后面增加一个节点，用来拷贝原节点的信息，这样我们通过原节点就可以很轻松的找出各个节点的random了。而这种方法的时间复杂度为O(N)，效率很高，所以我们选择这个方法。我们现在来实现一下这个方法。

typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) 
{//先将每一个节点都拷贝一遍并与它自己连接Node*pcur=head;while(pcur){Node*copy=(Node*)malloc(sizeof(Node));copy->val=pcur->val;copy->next=pcur->next;pcur->next=copy;pcur=copy->next;}//再将random拷贝pcur=head;while(pcur){Node*copy=pcur->next;if(pcur->random==NULL){copy->random=NULL;}else{copy->random=pcur->random->next;}pcur=copy->next;}//利用尾插，将拷贝的链表分离出来pcur=head;Node*copyhead=NULL;Node*copytail=NULL;while(pcur){Node* copy=pcur->next;Node*next=copy->next;if(copyhead==NULL){copyhead=copytail=copy;}else{copytail->next=copy;copytail=copytail->next;}pcur=next;}return copyhead;}