请实现 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。

方法一：哈希表

 代码语言：cpp 

STL：unordered_map用法

/*
// 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* curr = head;unordered_map <Node*, Node*> map;while(curr!=nullptr){map[curr] = new Node(curr->val);    //遍历所有结点并复制，建立原结点到新结点的键值对映射curr = curr->next;}curr = head;while(curr!=nullptr){map[curr]->next = map[curr->next];  //利用哈希表查询，构建新结点的next指向map[curr]->random = map[curr->random];  //构建新结点的random的指向curr = curr->next;}return map[head];   //返回新链表的头结点}
};

18 / 18 个通过测试用例

状态：通过

执行用时: 4 ms

内存消耗: 11 MB

方法二：拆分拼接 

思路：

 

 代码语言：cpp

/*
// 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 * curr = head;while(curr != nullptr){ //复制结点，拼接Node *copy = new Node(curr->val);Node *behd = curr->next;curr->next = copy;copy->next = behd;curr = copy->next;}curr = head;while(curr != nullptr){ //构建random指向if(curr->random != nullptr)curr->next->random = curr->random->next;curr = curr->next->next;}curr = head->next;Node * res = curr;while(curr->next != nullptr){   //拆分成两个链表head->next = head->next->next;curr->next = curr->next->next;head = head->next;curr = curr->next;}head->next = nullptr;   //原链表的尾结点（原则上不处理也可以，但是报错）return res; //新链表头结点}
};

 18 / 18 个通过测试用例

状态：通过

执行用时: 12 ms

内存消耗: 10.9 MB