题目描述：
给你一个长度为 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作为传入参数。
题目链接：复制带随机指针的链表
解题思路：
有些系统会判断原链表有没有被修改，所以最好还是将原链表还原。
代码：
/** * 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* next = cur->next; struct Node* copy =(struct Node*)malloc(sizeof(struct Node)); copy->val =cur->val; cur->next = copy; copy->next = next; cur = 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 = cur->next->next; } //将拷贝节点和源节点分别按顺序链接好 cur = head; struct Node* copyHead = NULL, * copyTail = NULL; while(cur) { struct Node* copy = cur->next; struct Node* next = copy->next; cur->next = next; if(copyTail == NULL) { copyHead = copyTail = copy; } else { copyTail->next = copy; copyTail = copyTail->next; } cur = next; } return copyHead; }
