C语言每日一题（33）随机链表的复制
题目描述
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
思路分析
有很多小伙连题目都读不懂，更别说思路。下面我将进行解释：
其实就是一个关于链表的拷贝，像一般的单链表只需要遍历一遍复制即可，但这个链表多了一个随机指针random，它可以指向链表中的任意一个结点，包括它自己，同时也可以指向空。这时你可能会想到，将链表复制一遍放到新节点，再将random指向对应的源节点的位置不就行了？但题目要求复制链表中的指针都不应指向原链表中的节点 ，这就成了一个大问题。也就是说，如果碰到后面结点的random在它之前，且不知道是是什么位置，单纯的用什么所谓的双指针还是快慢指针都会很麻烦。
基于单链表，这题的最优解是：
将要复制的结点插入到每一个源节点的后面，记为copy，题目要求copy的random不能指回源节点，只能值向复制的结点，会发现，如果要取到对应的复制结点，例如原节点13的random指向7，那复制结点13也要指向复制的7，怎么取到呢，就是原结点13的random的next，是不是很巧妙？基于这个思路，即复制结点的random就是原结点的random的next值。
方法步骤：
1.将需要复制的结点插入到原结点的后面。
2.将复制结点的random指向原结点的random的next值。
3.将链表取下，恢复原链表。
struct Node* copyRandomList(struct Node* head) {
struct Node* cur=head;//保存头结点，用cur遍历
while(cur)
{
struct Node* copy=(struct Node*)malloc(sizeof(struct Node));//复制结点用malloc创建
copy->val=cur->val;//
copy->next=cur->next;//进行插入
cur->next=copy;
cur=copy->next;//往下走
}
cur=head;//再从头走一遍
while(cur)//处理random指针
{
struct Node* copy=cur->next;
struct Node* next=copy->next;
if(cur->random==NULL)
{
copy->random=NULL;
}
else
{
copy->random=cur->random->next;
}
cur=next;
}
cur=head;
struct Node* newhead=NULL,*tail=NULL;
while(cur)//将复制完后的链表取下
{
struct Node* copy=cur->next;
struct Node* next=copy->next;//保存原链表的next值
if(newhead==NULL)//尾插
{
newhead=tail=copy;
}
else
{
tail->next=copy;
tail=tail->next;
}
cur->next=next;//恢复原链表
cur=next;//往下走
}
return newhead;//返回新节点
}