复杂链表节点结构：
让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：申请域名、虚拟空间、营销软件、网站建设、丰满网站维护、网站推广。
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* CopyComplexLinkList(ComplexNode * pHead) { if(pHead != NULL) //判空 { CloneNodes (pHead); //复制节点并连接在其后面 UpdateNewNodeRandom(pHead); //更新新节点的随机指针 return DisconnectNewNode (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<<"("<_data<<","<_random->_data<<")"<<"->";
cur = cur->_next;
}
cout<<"Nvl."<测试代码：
void Test()
{
ComplexNode* head = CreatList();
Print(head);
cout<<"---------------------------------------"<测试结果：
总结：复杂链表的复制分为三步：第一步就是把新复制出来的节点插入源链表中，第二步修改新插入节点的随机指针，第三步就是将新节点从源中拆分出来，并合并成一个新链表。
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
文章题目：C++复杂链表的复制-创新互联
文章URL：http://bjjierui.cn/article/csijpd.html
