复杂链表节点结构：

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

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

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

图示：

代码实现：

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

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

代码实现：

voidUpdateNewNodeRandom(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;}returnpNewHead;//返回新链表的头结点}

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

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

创建复杂链表：

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

打印链表：

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

测试代码：

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

测试结果：

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