题目难度：较难

题目描述：

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。 下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针，虚线箭头表示random指针。为简单起见，指向null的指针没有画出。

示例: 输入:{1,2,3,4,5,3,5,#,2,#} 输出:{1,2,3,4,5,3,5,#,2,#} 解析:我们将链表分为两段，前半部分{1,2,3,4,5}为ListNode，后半部分{3,5,#,2,#}是随机指针域表示。 以上示例前半部分可以表示链表为的ListNode:1->2->3->4->5 后半部分，3，5，#，2，#分别的表示为 1的位置指向3，2的位置指向5，3的位置指向null，4的位置指向2，5的位置指向null 如下图:

思路1:双指针

时间复杂度：O(n)，空间复杂度：O(1) 运行时间：3ms 占用内存：524KB

class Solution {
public;
  	RandomListNode* Clone(RandomListNode* pHead) {
      
      	if(!pHead) return pHead;
      
      	RandomListNode *cur = pHead;
      
      	while(cur) {
          	RandomListNode *clone = new RandomListNode(cur->label);
          	cur->next = clone;
          	cur = clone->next;
        }
      
      	cur = pHead;
      	RandomListNode *clone = phead->next;
      	RandomListNode *res = phead->next;
      
      	while(cur) {
          	if(!cur->random) cur->next->random = nullptr;
          	else clone->random = cur->random->next;
          
          	cur = cur->next->next;
          	if(clone->next) clone = clone->next->next;
        }
      
      cur = pHead;
      clone = pHead->next;
      	while(cur) {
          	cur->next = cur->next->next;
          	cur = cur->next;
          
          	if(clone->next) clone->next = clone->next->next;
          	clone = clone->next;
        }
      
      	return res;
    }
}

思路2:哈希表

时间复杂度：O(n)，空间复杂度：O(n) 运行时间：3ms 占用内存：524KB

class Solution {
public:
  	RandomListNode* Clone(RandomListNode* pHead) {
      	if(!pHead) return nullptr;
      
      	unordered_map<RandomListNode*, RandomListNode*> hashMap;
      	RandomListNode *res = new RandomListNode(0);
      	RandomListNode *cur = pHead;
      	RandomListNode *pre = res;
      
      	while(cur) {
          	RandomListNode *clone = new RandomListNode(cur->label);
          	hashMap[cur] = clone;
          
          	pre->next = clone;
          	pre = pre->next;
          
          	cur = cur->next;
        }
      
      	for(auto node : hashMap) {
          	if(!node->random) node.second->random = nullptr;
          	else node.second->random = hashMap[node.first->random];
        }
      	return res->next;
    }
}

😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘