题目描述：
给你一个长度为 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 作为传入参数。
思路：
题目要求我们拷贝一个带next指针与random随机访问指针的链表。
如果拷贝一个只带next指针的链表话呢，很简单，根据next依次遍历目标链表，再依次拷贝每个节点的信息就可以了.
一步一步来，我们可以先根据next“这条线” 先拷贝一个新的链表出来。
为什么不是优先根据random指针来拷贝呢？
这是因为random指针指向的是随机节点，可能有环存在，而且，random指向的节点有可能是很后面才出现的节点，而next在题目给出节点目标信息时关系就确定是线性不成环的，所以我们优先考虑拷贝next联系。
如何拷贝各个节点的random联系呢？--本题重点
首先，我们假设每一个random关系是一条有向边，在旧链表中存在random关系(A)-->(B),
那么对应的，我们想让复制出来的新链表也有这么一条边，且为(a)-->(b)
那么如果我们能通过（A）找到（a）,通过（B）找到（b）,在遍历旧链表的random关系链中，我们就能顺便建立复制体的关系。（其中节点a是A的复制节点，b是B的复制节点）
也就是说，只要我们能通过某种联系找到自己的复制体，那么我们就能复制random联系。
于是题目的关键转移到了如何将这种联系该存下来且能快速找到呢？
根据哈希思想给出以下解法：
解法一：
如果是c++的话，可以用STL库中的map容器来存下旧链节点在新链的复制体节点。
也就是达到hash[A]=a,hash[B]=b.
unordered_map<Node *, Node *> Hash({{NULL, NULL},{head, newhead}});
我这里照顾只学了c语言的朋友，主要讲方法二，不用map容器。
解法二：
改变旧链表的next,使其在被复制完后指向对应的复制体节点。
这里说的复制完是指复制val信息，以及next联系.
在复制next信息时，假设遍历到了A节点，首先用一个临时遍历temp存放A->next。
当我们创造出来了复制体a节点，我们让A->next=a,然后，a->random=A->random.
在将temp里的节点取出来继续遍历。
为什么要 a->random=A->random？
这是因为由于我们已经破坏了目标链表的next关系，我们之后再想复制random关系就不能再遍历旧链表了，仅依靠random关系可能出现环等问题，所以要想复制random关系，我们就要遍历新链表，也就是刚被复制出来的不完全体。
遍历到当前节点a,我们想要找a 的random应该指向哪里，我们可以先找到A的random指向的B，再通过B->next找到b，又因为A的random终点已经被赋给了a->random，所以就有了最重要的一步：
a->random=a->random->next.
这里a->random->next就是指向b节点。
重复以上步骤，就可以将所有random关系复制下来。
解法三：
思路和方法二差不多，只不过是将a->next=A -->next 然后A->next=a.这样一来，在破坏旧链的next关系后我们通过依旧可以通过A->next->next找到原来A的下一个节点。
这样我们再将a->random=A->random->next（先在目标链中找到B,再通过B->next找到b）.
这个方法只不过是恢复了旧链的可遍历性而已，和方法二差不多。
代码：
#define _CRT_SECURE_NO_WARNINGS 1 struct Node* copyRandomList(struct Node* head) { if (head == NULL)return NULL; struct Node* phead = head; struct Node* newhead = (struct Node*)malloc(sizeof(struct Node));//新链的头指针 struct Node* np = newhead; struct Node* star = newhead; while (phead) { struct Node* t = phead->next;//临时变量，存放phead的下一个节点，防止丢失 newhead->val = phead->val; newhead->random = phead->random;//为了方便后续建立random联系 phead->next = newhead;//哈希的思想，建立新、旧两个节点的联系 if (t == NULL) {//如果下一个节点是NULL,就不用开辟空间了 newhead->next = NULL; } else {//否则就创造一个节点空间，建立next关系 newhead->next = (struct Node*)malloc(sizeof(struct Node)); newhead = newhead->next; } phead = t; } while (np != NULL) { if (np->random != NULL) { np->random = np->random->next;//通过旧链找到新链应该指向的节点 } np = np->next; } return star; }
总结：
这个题总的来说不难，如果想用c写出来的话就要求对链表比较熟悉，还是比较考验基本功滴！
