C++ 复杂链表的复制

复杂链表节点结构：

struct ComplexNode {     ComplexNode(const int& d)         :_data(d)         ,_next(NULL)         ,random(NULL)     {}     int _data;            //数据域     ComplexNode* _next;               //指向下一节点     ComplexNode* _random;             //指向随机节点 };

复制复杂链表可以分为三步来完成：

第一步：将新复制的节点插入到原来链表当中（插入到原节点后面）

图示：

代码实现：

void CloneNodes(ComplexNode* pHead) {	ComplexNode* cur = pHead;	while(cur)	{	ComplexNode* NewHead = new ComplexNode();	//开辟新节点	NewHead->_data = cur->_data;	NewHead->_next = cur->_next;	NewHead->_random = NULL;	cur->_next = NewHead;	//连接新节点	cur = NewHead->_next;	//跳转到下一个要复制的节点	} }

第二步：修改新开辟的节点的_random，新的_random其实就是旧的_random的_next（新开辟的节点链在原来节点的后面，所以就是旧的_random->_next）

代码实现：

void UpdateNewNodeRandom(ComplexNode* pHead) {	ComplexNode* cur = pHead;	while(cur)	{	ComplexNode* next = cur->_next;	//指向新节点	if(cur->_random != NULL)	//优化：随机指针不为空时，复制	{	next->_random = cur->_random->_next;	//复制随机指针	}	cur = next->_next;	//下一个要复制的节点	} }

第三步：将复制出来的链表拆分出来

代码实现：

ComplexNode* DisconnectNewNode(ComplexNode* pHead) {	ComplexNode* cur = pHead;	//指向原来的节点	ComplexNode* next = NULL;	//指向复制出来的节点	ComplexNode* pNewHead = NULL;	//新链表的头节点	if(cur != NULL)	{	pNewHead = next = cur->_next;	//指向新链表的头	cur->_next = next->_next;	//将新节点分离	cur = next->_next;	}	while(cur)	{	next->_next = cur->_next;	//往复制出的链表上面连接新节点	next = next->_next;	//分离新节点	cur->_next = next->_next;	cur = next->_next;	}	return pNewHead;	//返回新链表的头结点 }

最后复制复杂链表就转化下面代码：

ComplexNode<T>* CopyComplexLinkList(ComplexNode<T>* pHead) {	if(pHead != NULL)	//判空	{	CloneNodes<T>(pHead);	//复制节点并连接在其后面	UpdateNewNodeRandom(pHead);	//更新新节点的随机指针	return DisconnectNewNode<T>(pHead);/    /拆分链表并返回新链表的头结点	}	return NULL; }

创建复杂链表：

ComplexNode* CreatList() {	ComplexNode* Node1 = new ComplexNode(1);    //创建节点	ComplexNode* Node2 = new ComplexNode(2);	ComplexNode* Node3 = new ComplexNode(3);	ComplexNode* Node4 = new ComplexNode(4);	ComplexNode* Node5 = new ComplexNode(5);	Node1->_next = Node2;       //连接节点	Node2->_next = Node3;	Node3->_next = Node4;	Node4->_next = Node5;	Node1->_random = Node3;    //置_random	Node2->_random = Node4;	Node3->_random = Node1;	Node4->_random = Node5;	Node5->_random = Node2;	return Node1;            //返回头 }

打印链表：

void Print(ComplexNode* _head) {	ComplexNode* cur = _head;	while(cur)	{	cout<<"("<<cur->_data<<","<<cur->_random->_data<<")"<<"->";	cur = cur->_next;	}	cout<<"Nvl."<<endl; }

测试代码：

void Test() {	ComplexNode* head = CreatList();	Print(head);	cout<<"---------------------------------------"<<endl;	ComplexNode* NewHead = CopyList(head);	Print(NewHead); }

测试结果：

总结：复杂链表的复制分为三步：第一步就是把新复制出来的节点插入源链表中，第二步修改新插入节点的随机指针，第三步就是将新节点从源中拆分出来，并合并成一个新链表。