本文共 2522 字，大约阅读时间需要 8 分钟。

复杂链表的复制。一个链表的每个节点，有一个指向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->next就可以了），只要能够复制random，再将这个链表拆开就可以了

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

#include 
   
    	#include 
    
     	#include 
     
      	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;	}