浅谈复杂链表的复制

链表是一种很常见的数据结构，单链表、双向链表、循环链表和复杂链表都是其衍生物。复杂链表之所以命名为复杂链表，也正是由于其结构的复杂。它比其他其他种类的链表多了一个指针域，这个指针域可以指向链表中的任一结点，也可以为空。

其结构定义如下：

struct ComplexNode
{
	DataType _data;
	struct ComplexNode * _next;
	struct ComplexNode * _random;//随机域
};

结构示例：

ps：蓝色指针为next域，红色为random域。

接下来就要思考如何复制了。复制一个单链表很简单，所以问题的难点就在于如何复制它的随机指针域。

首先想到的就是先将原始链表的每一个结点复制下来，并用next连接，使其先成为一个单链表。接下来，就是考虑如何复制random域了。由于这个指针可以指向链表中的任何一个指针，所以必须从头遍历整个链表才可以找到这个指针。可以采取这样一种方式，就是先遍历原始链表，数出其到random是多少步，然后记下，让复制的链表也进行相同的步数找到其random指向的结点。这样就可以复制random指针了。这种方法需要对n个结点遍历n次才可以。时间复杂度为O（n^2）。

尝试对其进行优化。

Step1——>要做的还是将链表的每个结点复制下来，并将其连在原始链表的后面，先将其random域赋为空。

代码实现：

void CopyNode(ComplexNode *pHead)
{
	ComplexNode *pNode=pHead;
	while(pNode!=NULL)
	{
		ComplexNode *pCopy=new ComplexNode;
		pCopy->_data=pNode->_data;
		pCopy->_next=pNode->_next;
		pCopy->_random=NULL;
		pNode->_next=pCopy;
		pNode=pCopy->_next;
	}
}

Step2——>拷贝random域。由于已经将复制的结点连接在相应的原始结点的后面。所以复制的结点的random域也是原始结点对应的random域的下一个指针。

代码实现;

void ConnectRandom(ComplexNode *pHead)
{
	ComplexNode *pNode=pHead;
	while(pNode!=NULL)
	{
		ComplexNode *pCopy=pNode->_next;
		if(pNode->_random!=NULL)
		{
			pCopy->_random=pNode->_random->_next;
		}
		pNode=pCopy->_next;
	}
}

Step3——>将链表拆分为两个部分，也就是将原始链表和复制链表分开。返回的是复制的链表。

ComplexNode* SplitList(ComplexNode *pHead)
{

    ComplexNode *pCloneHead = pHead->_next;
    ComplexNode *tmp;	   
    ComplexNode *cur = pHead;
        while(cur->_next)
		{
            tmp = cur->_next;
            cur->_next =tmp->_next;
            cur = tmp;
        }
        return pCloneHead;
}