题目描述：
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针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,2,3,4,5,3,5,#,2,#}
返回值：
{1,2,3,4,5,3,5,#,2,#}
解题思路：
本题考察数据结构链表的使用。本题常用两种解法。
- 哈希表。用哈希map创建一个映射表，建立哨兵防止前指针为空，pre用来搭建新链表，cur用来遍历原链表；遍历存储映射关系，就如原链表的第二个结点对应新链表的第二个结点，一一对应，有点像“影子模仿术”；映射完成后，对哈希表进行遍历，value对应新链表，key对应原链表，value的random等于m[key->random]就相当于，让新链表的random照着原链表的random进行连接（注意这里的key->random指向原链表的结点，m[key->random]才是指向新链表的结点）；删除哨兵，新链表复制完毕。
- 链表拆分法。第一遍遍历链表，每个结点后面创建一个结点，形成组合链表；第二遍遍历组合链表，将新链表结点的random连接至原链表结点random的next即可，实现同步连接；第三遍遍历组合链表，进行拆分工作，将指针next连接至next的next，相当于把组合链表拆分为原链表和新链表，此时新链表已经完成。
测试代码：
解法一：哈希表
/* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) { } }; */ class Solution { public: RandomListNode* Clone(RandomListNode* pHead) { // 若为空则返回 if(!pHead) return pHead; // 创建哈希map unordered_map<RandomListNode*, RandomListNode*> m; // 建立哨兵，防止前指针为空 RandomListNode* sentry=new RandomListNode(0); // 建立指向哨兵和表头的指针 RandomListNode* pre=sentry,*cur=pHead; // 遍历存储映射关系 while(cur) { RandomListNode* temp = new RandomListNode(cur->label); pre->next = temp; m[cur] = temp; pre = pre->next; cur = cur->next; } // 遍历哈希表，将新表的random参考原表的random关系进行连接 for(auto&[key,value]:m) { value->random=key->random==NULL?NULL:m[key->random]; } // 删除哨兵 delete sentry; return m[pHead]; } };
解法二：链表拆分
class Solution { public: RandomListNode* Clone(RandomListNode* pHead) { // 为空则返回 if(!pHead) return pHead; // 遍历链表 RandomListNode* cur = pHead; // 每个结点后面创建一个复制结点 while(cur){ RandomListNode* tmp = new RandomListNode(cur->label); tmp->next = cur->next; cur->next = tmp; cur = tmp->next; } // 遍历组合链表，将原链表的random的next与新链表结点的random连接 RandomListNode *old = pHead, *clone = pHead->next, *ret = pHead->next; while(old){ clone->random = old->random == NULL ? NULL : old->random->next; // 处理拷贝节点的随机指针 if(old->next) old = old->next->next; // 注意特判空指针 if(clone->next) clone = clone->next->next; } // 再次遍历，进行拆分，间隔拆分，拆出原链表和新链表 old = pHead, clone = pHead->next; while(old){ // 拆分链表 if(old->next) old->next = old->next->next; if(clone->next) clone->next = clone->next->next; old = old->next; clone = clone->next; } return ret; } };
