深拷贝，是指将该链表除了正常单链表的数值和next指针拷贝，再将random指针进行拷贝
想法一
先拷贝出一份链表，再对于每个节点的random指针，在原链表进行遍历，找到random指针的指向，最后完成拷贝链表random的指向
时间复杂度：O(N^2)
想法二
下面这种方法，是使用C语言的最优解
时间复杂度：O(N)
完整代码如下：
struct Node* copyRandomList(struct Node* head) { //1.拷贝节点插入原节点的后面 struct Node* cur = head; while (cur) { struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; struct Node* next = cur->next; copy->next = next; cur->next = copy; cur = next; } //2.控制拷贝节点的random cur = head; while (cur) { struct Node* copy = cur->next; if (cur->random) { copy->random = cur->random->next; } else { copy->random = NULL; } cur = copy->next; } //3.拷贝节点解下来组成拷贝链表，恢复原链表 cur = head; struct Node* copyHead = NULL; struct Node* copyTail = NULL; while (cur) { struct Node* copy = cur->next; struct Node* next = copy->next; if (copyTail) { copyTail->next = copy; copyTail = copyTail->next; } else { copyHead = copyTail = copy; } cur->next = next; cur = next; } return copyHead; }
