题目描述：

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

实现如下：

//老样子，在线测试用例依旧是无头链表。。。→_→
//本题可以利用辅助内存以空间换取时间
//第一次遍历：在原链表的每一个节点之后添加一个与它值相同的新节点，此时完成next指针域的构建
//第二次遍历：每一个newNode的随机指针域为它前一个节点的随机指针域的next，此时完成随机指针域的构建
//第三次遍历：将链表拆分成两个独立链表，一个为原链表，一个为复制链表
//注意：
//1.特殊情况判断：链表为空
//2.仔细思考指针的操作！
//3.在线测试用例必须保证原链表完整！在这被坑了好久。。。
//4.这道题的在线测试，就不用释放内存了。。。
/*
struct RandomListNode 
{
	int label;//值域
	struct RandomListNode *next, *random;//next指针域和随机指针域
	RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
};
*/
class Solution 
{
public:
	RandomListNode *cloneHead = NULL;//保存复制链表head
	RandomListNode* createNode(int label)//创建新节点
	{
		RandomListNode *p = (RandomListNode*)malloc(sizeof(RandomListNode));
		assert(p != NULL);
		memset(p, 0, sizeof(RandomListNode));
		p->label = label;
		return p;
	}
	void freeNode(RandomListNode *p)//虽然用不到但还写出来
	{
		free(p);
	}
	void cloneLinkList(RandomListNode* pHead)//第一次遍历：构建next
	{
		RandomListNode *newNode = NULL;
		while (pHead != NULL)
		{
			newNode = createNode(pHead->label);
			newNode->next = pHead->next;
			pHead->next = newNode;
			pHead = newNode->next;
		}
	}
	void perfectLinkList(RandomListNode *pHead)//第二次遍历：构建随机指针域
	{
		while (pHead != NULL)
		{
			if (pHead->random != NULL)//有可能这个节点的随机指针域为NULL
				pHead->next->random = pHead->random->next;//新节点的随机指针域为其前一个节点的随机指针域的next
			pHead = pHead->next->next;
		}
	}
	void divisionLinkList(RandomListNode* pHead)//第三次遍历：拆分链表为两个自链表
	{
		RandomListNode *tmp = pHead;
		cloneHead = pHead->next;//记录复制链表head
		pHead = cloneHead->next;
		while (pHead != NULL)
		{
			tmp->next->next = pHead->next;
			tmp->next = pHead;
			tmp = pHead;
			pHead = pHead->next->next;
		}
		tmp->next = NULL;//最后要将原链表的最后一个节点的next置为NULL
	}
	RandomListNode* Clone(RandomListNode* pHead)
	{
		if (pHead == NULL) return cloneHead;//防御性动作
		cloneLinkList(pHead);
		perfectLinkList(pHead);
		divisionLinkList(pHead);
		return cloneHead;
	}
};