复杂链表的复制

何为复杂链表呢？

    在复杂链表中，每个结点除了有一个_next指针指向下一个结点，还有一个_random指向链表中的任意结点或者NULL。结点定义如下：

template <class T>
struct ComplexNode
{
public:
	ComplexNode(const T&d)
		:_data(d)
		,_next(NULL)
		,_random(NULL)
	{}
public:
	T _data;//数据
	ComplexNode* _next;//指向下一个节点
	ComplexNode* _random;//指向随机节点或者NULL
};

如图是一个含有5个结点的复杂链表。实线箭头为_next指针，虚线为_random指针。

看到此问题时，首先会想到把复制过程分成两部分：第一步是复制原始链表上的每一个节点，并用_next连接起来；第二步是设置每个节点的_random指针。假设原始链表中的节点N的_random指向节点S，由于S节点的位置可能在N的前面，也有可能在N的后面。所以要定位S的位置需要从头开始查找。如果从开始链表的头结点开始沿着_next经过n步找到节点S，那么在复制链表中节点N‘的_random离复制链表的头结点的距离也是n步。若有n个节点，为每个节点查找_random时，都需要从头结点开始查找。因此此方法的时间复杂度度为O（n^2）。

由于上面一种方法的时间主要花费在查找节点的_random上面。可以从这方面去优化。

第一步：根据原始链表的每一个节点N创建对应的N’，并连接在N后。（如图所示）

第二步：设置复制出来节点的_random。假设原始链表上的节点N的_random指向节点S，由图可以看出，N‘的_random是N的_random的_next指向的节点。（红线所示）第三步：拆分链表。把奇数位上的节点用_next连接起来就是原始链表，把偶数位上的节点用_next连接起来即为复制后的节点。

由此看来，时间复杂度为O（n）。

接下来，实现第二种思路。

第一步：复制节点

template <class T>
void CopyNode(ComplexNode<T>* pHead) //复制节点
{
	ComplexNode<T>* cur = pHead;
	while(cur)
	{
		ComplexNode<T>* pClone = new ComplexNode<T>(cur->_data);//创建新的节点
		pClone->_next =  cur->_next;
		pClone->_random = NULL;

		cur->_next = pClone;
		cur = pClone->_next;
	}
}

第二步：设置复制出来的节点的_random

template <class T>
void RandomNode(ComplexNode<T>* pHead)//找_random
{
	ComplexNode<T>* cur = pHead;
	ComplexNode<T>* pClone = pHead->_next;
	while(pClone->_next)
	{
		if(cur->_random != NULL)
		{
			pClone->_random = cur->_random->_next;//复制节点的_random为原始节点的_random指针的_next
		}

		cur = pClone->_next;
		pClone = cur->_next;
	}
}

第三步：拆分链表

template <class T>
ComplexNode<T>* ConnectNode(ComplexNode<T>* pHead)//拆分链表
{
	ComplexNode<T>* cur = pHead;//奇数位
	ComplexNode<T>* pCloneNode = pHead->_next;//偶数位
	ComplexNode<T>* pCloneHead = pHead->_next;
	while(pCloneNode->_next)
	{
		cur->_next = pCloneNode->_next;//原始节点链接
		cur = cur->_next;

		pCloneNode->_next = cur->_next;//复制后节点的链接
		pCloneNode = pCloneNode->_next;
	}
	return pCloneHead;
}

创建复制链表：

template <class T>
ComplexNode<T>* CreatNode(ComplexNode<T>* pHead)//构造复杂链表
{
	ComplexNode<T>* Node1 = new ComplexNode<T>(1);
	ComplexNode<T>* Node2 = new ComplexNode<T>(2);
	ComplexNode<T>* Node3 = new ComplexNode<T>(3);
	ComplexNode<T>* Node4 = new ComplexNode<T>(4);
	ComplexNode<T>* Node5 = new ComplexNode<T>(5);

	pHead = Node1;

	Node1->_next = Node2;
	Node2->_next = Node3;
	Node3->_next = Node4;
	Node4->_next = Node5;

	Node1->_random = Node3;
	Node2->_random = Node5;
	Node4->_random = Node2;
	return pHead;
}

打印链表：

template <class T>
void PrintNode(ComplexNode<T>* pHead)//打印
{
ComplexNode<T>* cur = pHead;
while(cur)
{
cout<<cur->_data<<" ";
if(cur->_random)//若_random不为空
{
cout<<cur->_random->_data;
}
cout<<"->";
cur = cur->_next;
}
cout<<endl;
}

主函数实现：

int main()
{
	ComplexNode<int>* head = NULL;
	ComplexNode<int>* ret = CreatNode(head);//创建复杂链表
	cout<<"原来的链表："<<endl;
	PrintNode(ret);
	CopyNode(ret);//复制节点
	RandomNode(ret);//链接复制后节点的_random
	ComplexNode<int>* tmp = ConnectNode(ret);//拆分节点
	cout<<"复制后的链表："<<endl;
	PrintNode(tmp);
	return 0;
}

测试结果：

本文出自 “一起去看星星” 博客，转载请与作者联系！

复杂链表的复制

原文：http://10810429.blog.51cto.com/10800429/1764455