复杂链表的复制

复杂链表的复制。一个链表的每个节点，有一个指向next指针指向下一个结点，还有一个random指针指向这个链表中的一个随机节点或者NULL，现在要求实现复制这个链表，返回复制后的新链表。

题目的意思可以简化，就是一个节点含有两个指针和一个数据。用图表示：

如果要实现复杂链表的复制，我们通常的想法和单链表的复制一样，先按照next进行复制，然后在复制random（注：这种事错误的，不能实现）。为什么不能实现？
我们按照代码来实现一下：

	void Copy错误的示范(CNode *list)
	{
		CNode *cur = list;
		CNode *newNode;
		CNode *result = NULL;	// 指向新链表的第一个结点
		CNode *tail = NULL;	// 指向新链表的最后一个结点

							// 按普通链表的方式复制了一份链表
							// 再按尾插的方式，把新结点插入到新的链表中
		//将单链表按照next进行复制
		for (; cur != NULL; cur = cur->next) {
			// 遍历原链表的每个结点，根据其 data 值，创建新结点	// 遍历原链表的每个结点，根据其 data 值，创建新结点
			newNode = CreateNode(cur->data);
			if (tail != NULL) {
				tail->next = newNode;
			}
			else {
				result = newNode;
			}
			tail = newNode;
		}
		//然后开始复制random
		cur = list;
		for (newNode = result; cur != NULL; newNode = newNode->next) 
		{
			newNode->random = cur->random;
			cur = cur->next;
		}
	}

上面的代码在按next复制都没有问题，但如果再按照random进行复制就会出现问题:

如上图：所以，不能够按照普通复制单链表的方式来复制复杂链表
那么，就要换一种思想：就是如何解决上面的那个问题，就要能够通过老链表的random来找到新链表的random，那我们是不是可以将两个链表连在一起，如下图：

按照这样的链表，我们就能够通过上面的random，来找到下面的random（让上面的random->next就可以了），只要能够复制random，再将这个链表拆开就可以了
总结：

• 第一步：复制每个节点，让老节点跟在新节点的后面
• 第二步：复制random newNode->random = oldNode->random->next
• 第三步：拆分链表

	#include <stdio.h>
	#include <stdlib.h>
	#include <assert.h>
	typedef int DataType;

	typedef struct CNode
	{
		DataType data;
		struct CNode *next;
		struct CNode *random;
	}CNode;

	CNode *CreateNode(DataType data)
	{
		CNode *node = (CNode *)malloc(sizeof(CNode));
		node->data = data;
		node->next = NULL;
		node->random = NULL;
		return node;
	}

	CNode *CListInit()
	{
		CNode *n1 = CreateNode(1);
		CNode *n2 = CreateNode(2);
		CNode *n3 = CreateNode(3);
		CNode *n4 = CreateNode(4);

		n1->next = n2;
		n2->next = n3;
		n3->next = n4;
		n1->random = n3;
		n2->random = n1;
		n3->random = n3;
		return n1;
	}

	void CNodeCopy(CNode *list)
	{
		assert(list);
		CNode *cur = list; //cur指向老节点
		CNode *newNode = NULL;  //newNode指向新节点
		CNode *result = newNode; //result指向新链表的头结点
		//第一步
		while (cur != NULL)
		{
			newNode = CreateNode(cur->data);
			newNode->next = cur->next;
			cur->next = newNode;
			cur = newNode->next;
		}
		cur = list;
		result = list->next;
		//第二步
		while (cur->random != NULL)
		{
			newNode = cur->next;
			newNode->random = cur->random->next;
			cur = newNode->next;
		}
		cur = list;
		newNode = cur->next;
		//第三步
		while (cur != NULL)
		{
			cur->next = newNode->next;
			cur = cur->next;
			if (cur != NULL)
			{
				newNode->next = cur->next;
			}
			newNode = newNode->next;
		}
	}

	void test()
	{
		CNode *CList = CListInit();
		CNodeCopy(CList);
	}

	int main()
	{
		test();
		system("pause");
		return 0;
	}