请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]] 示例 2：
输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]] 示例 3：
输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]] 示例 4：
输入：head = [] 输出：[] 解释：给定的链表为空（空指针），因此返回 null。
提示：
-10000 <= Node.val <= 10000 Node.random 为空（null）或指向链表中的节点。 节点数目不超过 1000 。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路一：利用hash_map来实现，首先将原来的节点记为N，要复制的节点记为N',构建一个hash_map<N,N'>,即可以利用N(原来链表)索引到当前链表N',那么我们在连接时，根据原来链表进行索引就可以知道要连接到哪里去了。
/* // 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: unordered_map<Node*,Node*> hash_map; Node* copyRandomList(Node* head) { Node* cur = head; while(cur)//第一次遍历构建hast_map表 { hash_map[cur] = new Node(cur->val); cur = cur->next; } cur = head; while(cur) { hash_map[cur]->next = hash_map[cur->next]; hash_map[cur]->random = hash_map[cur->random]; cur = cur->next; } return hash_map[head]; } };时间复杂度：O(n) 空间复杂度：O(n)
思路二：实际上我们可以不需要使用hashmap的辅助空间O(n)，从而直接在原来链表上构建复制链表，这也是剑指offer书上本来给的思路。
复制一个新的节点在原有节点之后，如 1 -> 2 -> 3 -> null 复制完就是 1 -> 1 -> 2 -> 2 -> 3 - > 3 -> null从头开始遍历链表，通过 cur.next.random = cur.random.next 可以将复制节点的随机指针串起来，当然需要判断 cur.random 是否存在将复制完的链表一分为二 根据以上信息，我们不难写出以下代码： /* // 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) { Node* copyNode = new Node(cur->val); copyNode->next = cur->next; cur->next = copyNode; cur = cur->next->next;//转向到原来链表的下一个节点 } //完成随机链表的复制 cur = head; while(cur) { if(cur->random)//必须有才可以连接 random默认构造已经是null { //原来链表的random的下一个节点就是复制链表的random要指向的地方 cur->next->random = cur->random->next; } cur = cur->next->next;//依然是在原来链表上跳过两个节点 } //将链表再分开 Node* copyHead = head->next; cur = head; Node* curCopy = head->next; while(cur) { cur->next = cur->next->next;//将原来链表提取出来 cur = cur->next; if(curCopy->next) { curCopy->next = curCopy->next->next;//在复制链表上跳过原来节点 curCopy = curCopy->next;//跳到下一个节点 } } return copyHead; } };