题目: 

给你一个长度为 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 作为传入参数。

 好了，我们正式来解读下这个题目，如果没有random,好像很简单。直接复制就完事了,如图所示

 但事实上我们还要加一个random，上一张图里复制的7的结点，与原链表没有联系，所以很难找到random。所以重新连接下链表。

 如图，我们每次复制一个结点都会将原结点的next指向复制的结点，然后将复制的结点的next指向下一个原结点上，依次类推下去，就完成了上图的链表。想一想，我们怎么按照上面的图找出复制结点的random,看下，如果我要找7的random，我们看下他前面的原结点，他的random指向的是NULL，然后我们的复制结点的random也就指向 NULL，这是个例外，我们在来看下一个结点，怎么找结点为13的random，同样的我们来看下，它复制的原结点的random指向的结点的next是不是就是复制结点要找的7.同样的依次找下去，就可以完成这一任务。

接下来我们要做的就会把之前连接在一起的链表给分开，最后返回复制链表的头指针即可。

/**
 * 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=copy->next;
    }
    //接下来寻找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 Node*copyHead=NULL;
    struct Node*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=copy;
        }
     cur->next=next;
     cur=next;

    }
    return copyHead;
}