复制，就需要和原链表的地址不同，不能引用原地址，因此你需要开辟新的空间。
正常情况下，你只需要遍历下面，但现在是复杂链表，random指向任意的节点，所以
如果你只是遍历多次，你可能遇到指向的节点，在遍历时候还没有创建，或者创建成功了，每次去查找它，让时间复杂度何其复杂，所以我们要存储节点
这里，介绍两种方法
法1：哈希表
/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; } }; */ class Solution { public: Node* copyRandomList(Node* head) { if(head == nullptr) return nullptr; Node* cur = head; unordered_map<Node*, Node*> map; while(cur != nullptr){ map[cur] = new Node(cur->val); cur=cur->next; } cur = head; while(cur !=nullptr){ map[cur]->next = map[cur->next]; map[cur]->random = map[cur->random]; cur = cur->next; } return map[head]; } };
解析：
按实例，如果节点为空，直接输出null。
c++使用哈希表借助unordered_map,
我们先通过遍历创建哈希表，
例如，map[A] = A*
这里的A是指链表指针的原地址，A*注意了，是你重新开辟的值为A的节点！因为是复制，所以不能引用原地址。
然后再给新节点random和next指针引用新节点。这里的循环依旧通过原地址去映射找出新节点。
我这里，一开始的想法是：
map[cur]->next = cur->next; map[cur]->random = cur->random;
实际上，又引用了原节点，是错的，大家应该避免。
方法，拼接和拆分
原链表为，A->B->C
那我们就要创建A->A->B->B->C->C...
然后再把新创建的节点分离开，另一种存储节点的方式就是直接作用在原链表上，空间复杂度随之减少了。
/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; } }; */ class Solution { public: Node* copyRandomList(Node* head) { if (head == nullptr) return nullptr; Node* cur = head; // 复制新节点拼接，这里建议大家画图，能够更加清楚认识。 while(cur != nullptr) { Node* tmp = new Node(cur->val); tmp->next = cur->next; cur->next = tmp; cur = tmp->next; } cur = head; // 给新节点random和next指向，注意，你指向的需要是新节点，是next的next while(cur != nullptr){ if(cur->random != nullptr) cur->next->random = cur->random->next; cur = cur->next->next; } // 拆分 Node* pre = head,*res = head->next; cur = head->next; while(cur->next!=nullptr){ pre->next = pre->next->next; cur->next = cur->next->next; pre = pre->next; cur = cur->next; } // 这里只是为了完整，把原链表分离出来，最后指向null，而为什么新链表不用指了呢？ // 因为新链表用了原链表最后的null，在前面的创建中，新节点->null pre->next = nullptr; return res; } };
这里还要讨论两个while循环，为什么一个是判断cur!=nullptr,而另一个却是cur->next
起始点不一样，第一个是head，第二个是head->next因为复制在原链表的原因，旧节点后面必然接着新节点，所以cur的next必然有，如果cur是null，那自然不需要了。后面我们在分离，我们就要知道，实际我们判断的是cur/head的next的next，新链表最后必接了null，所以这样不会造成next的next，nul的next还是null的错误了。
