【数据结构】复杂链表的复制

实现复杂链表的复制。

因为复杂链表中每个节点都有一个指向任意节点的指针。所以在确定这个链表的复制的时候。我们需要进行空间来换取时间上的效率。然后我们可以将链表复制项结合在拆分。

思路就这样。

我直接给出代码：

#pragmaonce
#include<stdio.h>
#include<malloc.h>
#include<assert.h>

typedefintDataType;

typedefstructComplexNode
{
	DataType	_data;				//数据
	structComplexNode*_next;		//指向下一个节点的指针
	structComplexNode*_random;	//指向随机节点
}ComplexNode;

voidcreatComplexNode(ComplexNode*&pHead,DataTypex);
ComplexNode*CopyComplexNode(ComplexNode*pHead);
//创建复杂链表。
voidcreatComplexNode(ComplexNode*&pHead,DataTypex)
{
	ComplexNode*ret,*endNode;
	if(pHead==NULL)
	{
		pHead=(ComplexNode*)malloc(sizeof(ComplexNode));
		pHead->_random=NULL;
		pHead->_data=x;
		pHead->_next=NULL;
		return;
	}
	endNode=pHead;
	ret=endNode;
	while(endNode->_next)
	{
		ret=endNode;
		endNode=endNode->_next;
	}
	endNode->_next=(ComplexNode*)malloc(sizeof(ComplexNode));
	endNode=endNode->_next;
	endNode->_next=NULL;
	endNode->_data=x;
	endNode->_random=ret;
}

//解决复杂链表的复制。可以把其中的操作分为3个步骤：
//合并。
//复制随机指针值。
//拆分。
ComplexNode*CopyComplexNode(ComplexNode*pHead)
{
	ComplexNode*copyNode;
	ComplexNode*pNode=pHead;
	ComplexNode*newLink=NULL;
	ComplexNode*newNode=NULL;
	assert(pHead);
	while(pNode!=NULL)
	{
		copyNode=(ComplexNode*)malloc(sizeof(ComplexNode));
		copyNode->_data=pNode->_data;
		copyNode->_next=pNode->_next;
		copyNode->_random=NULL;

		pNode->_next=copyNode;
		
		pNode=copyNode->_next;
	}

	pNode=pHead;

	while(pNode!=NULL)
	{
		copyNode=pNode->_next;
		if(pNode->_random!=NULL)
		{
			copyNode->_random=pNode->_random->_next;
		}
		pNode=copyNode->_next;
	}

	pNode=pHead;
	newLink=pNode->_next;
	while(pNode!=NULL)
	{
		newNode=pNode->_next;
		pNode->_next=newNode->_next;
		pNode=pNode->_next;
		if(newNode->_next!=NULL)
			newNode->_next=pNode->_next;
	}
	returnnewLink;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!