138.随机链表的复制（LeetCode）

链表的复制（LeetCode）"/>

138.随机链表的复制（LeetCode）

深拷贝，是指将该链表除了正常单链表的数值和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.控制拷贝节点的randomcur = 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;
}