题目

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

算法原理

我们很容易能够根据next创建一个原链表的顺序链表，但是如何把random的指针指向正确的位置呢？我们很容易想到遍历的方法，如图所示：13的random指向7，那么我们只要遍历当结点的值满足7，再把13的random指向7就可以了，但是如果有两个结点的值是相同的这个方法就行不通了，而且这个方法的时间复杂度是O（n^2）。
这里我们介绍的方法是：建立原结点和拷贝结点之间的关系
1.拷贝结点值到原结点后面

2.控制拷贝结点的random：拷贝结点的random是原结点random->next
3.拷贝节点离开原结点，恢复原链表

代码实现

struct Node { int val;          // 定义节点的值struct Node* next;  // 指向下一个节点的指针struct Node* random; // 指向随机节点的指针
};struct Node* copyRandomList(struct Node* head) { // 定义一个当前节点的指针 cur，初始化为头节点 headstruct Node* cur = head; while (cur) { // 为新节点分配内存struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); // 将当前节点的值复制到新节点中copy->val = cur->val; // 获取当前节点的下一个节点struct Node* next = cur->next; // 将当前节点的下一个指针指向新复制的节点cur->next = copy; // 新复制节点的下一个指针指向原来的下一个节点copy->next = next; // 移动到下一个节点cur = next;// 控制拷贝节点的 randomcur = head; while (cur) { // 获取当前节点的下一个节点struct Node* copy = cur->next; // 判断当前节点的 random 是否为空if (cur->random == NULL) {  // 这里将 = 改为 ==// 如果为空，将新节点的 random 设置为 NULLcopy->random = NULL; } else { // 否则，将新节点的 random 设置为当前节点的 random 的下一个节点copy->random = cur->random->next; } // 移动到下一个节点cur = copy->next; } // 用于保存拷贝后链表的头节点struct Node* copyHead = NULL; // 用于保存拷贝后链表的尾节点struct Node* copyTail = NULL; while (cur) { // 获取当前节点的下一个节点struct Node* copy = cur->next; // 获取下一个节点struct Node* next = copy->next; // 如果尾节点为 NULLif (copyTail == NULL) { // 将头节点设置为当前节点copyHead = copyTail = copy; } else { // 将尾节点的下一个节点设置为当前节点copyTail->next = copy; // 更新尾节点为当前节点copyTail = copyTail->next; // 将当前节点的下一个节点设置为下一个节点cur->next = next; // 移动到下一个节点cur = next; } // 返回拷贝后链表的头节点return copyHead; } 
}