力扣138：随机链表的复制
题目描述：
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。 random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。 你的代码 只 接受原链表的头节点 head 作为传入参数。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]]
提示：
0 <= n <= 1000 -104 <= Node.val <= 104 Node.random 为 null 或指向链表中的节点。
分析：
这道题的意思是对一个 含有随机指针的单链表进行复制，也就是说，复制之后也是一个完全一样的含有随机指针的单链表。原来单链表中每个节点的随机指针指向的节点，在复制之后，依然 也得是一样的。
对于这道题，三步走：
- 第一步 拷贝节点在原节点后面：
将原链表中每个节点依次拷贝一份，并插入到对应节点后面。在遍历原链表时，cur用于记录原链表中当前节点。动态开辟一个copy节点，用于存储拷贝的节点。
在插入时，先执行copy->next=cur->next；再执行cur->next=copy。
完成依次拷贝并插入到对应节点后，将cur后移。这里的后移是在原链表上后移动，但是原链表的第一个节点在后面插了一个节点，因此cur一个需要移动两个节点，即cur=cur->next->next或者cur=copy->next。
什么时候遍历结束呢？
当前指针cur为空时，表示原来的链表遍历结束。
- 第二步：处理拷贝节点copy的random
原来链表的每个节点都有一个随机指针，因此在复制的时候，也要将随机指针赋值到拷贝的链表中。
以下面这个情况为例：
可以看到，第一个节点7的随机指针指向的是NULL，第二个节点13的随机指针指向的是第一个节点7，第三个节点11的随机指针指向的是第五个节点1…
当原链表节点的随机指针指向NULL时，那么我们对应的拷贝节点的随机指针也指向NULL，即copy->random=NULL
当原链表节点的随机指针指向另外一个节点时，可以使对应的拷贝节点copy指向当前节点cur随机节点指向的节点的下一个节点，即copy->random=cur->random->next，这一步是整个代码的灵魂，这里可能有点绕，结合下图去分析：
当前指针cur为空时，遍历结束。
- 第三步：拷贝节点copy解下来尾插：
这一步，主要使用是单链表中尾插操作。
需要先创建一个新的头指针和尾指针，当尾指针为空时，也就是说新链表里面还没有节点时，此时插入的节点就是这个新链表的头节点
遍历链表，当前指针cur为空时，遍历结束
拷贝指针copy所指向的节点，需要尾插到新链表里面，copy指针即copy=cur->next,实现尾插：tail->next=copy
将拷贝节点解下来后，还需要将原链表复原，因此，需要创建一个next指针指向copy->next,next也就是原链表的下一个节点。补原链表，cur->next=next
cur移动到next位置，继续执行上述操作，直到cur为空
最后只需要返回新链表的头节点，即拷贝后的链表。
代码：
/**
* Definition for a Node.
* struct Node {
* int val;
* struct Node *next;
* struct Node *random;
* };
*/
struct Node* copyRandomList(struct Node* head) {
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=cur->next->next;
}
cur=head;
while(cur)
{
struct Node*copy=cur->next;
if(cur->random==NULL)
{
copy->random=NULL;
}
else
{
copy->random=cur->random->next;
}
cur=cur->next->next;
}
struct Node* newhead=NULL,*tail=NULL;
cur=head;
while(cur)
{
struct Node*copy=cur->next;
struct Node*next=copy->next;
if(tail==NULL)
{
newhead=tail=copy;
}
else{
tail->next=copy;
tail=tail->next;
}
cur->next=next;
cur=next;
}
return newhead;
}