只有启程，才会达到理想和目的地
---》题目跳转
题目描述：
给你一个长度为 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的相对位置，然后malloc结点，一个一个链接起来，在通过相对位置找到自身的random,这样的思路时间复杂度是多少呢？
很明显这是典型的O(N^2),那么还有更好的思路吗？
第一步：复制原节点并且将复制的结点链接在原节点之后；
第二步：找到复制结点的random;
第三步：恢复链表。
听起来好像挺简单的，但是这个题整体考查了我们对链表增删查改的 拿捏度，每一步大家最好先是把图画好，然后有了大致思路再去撸代码，这样的效果会更加高效一些。
这里有个动图大家可以参考下：
具体代码：
struct Node* copyRandomList(struct Node* head) { //1 复制结点链接在原结点之后 struct Node* cur=head; while(cur) { struct Node* next=cur->next; struct Node* copy=(struct Node*)malloc(sizeof(struct Node)); copy->val=cur->val; cur->next=copy; copy->next=next; cur=next; } //2 链接随机指针 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; } //3 恢复链表，尾插数据 cur=head; struct Node* newHead=NULL,*newTail=NULL; while(cur) { struct Node* copy=cur->next; struct Node* next=copy->next; cur->next=next; if(newHead==NULL) newHead=newTail=copy; else { newTail->next=copy; newTail=newTail->next; } cur=next; } return newHead; }
每一步大家代码实现可能不一样，但是总体思路应该是差不多的，这道链表题能够很好的考察大家对链表的掌握情况，大家也快去试试吧！
