struct ComplexListNode { int m_nValue; Complex:istNode* m_pNext; ComplexListNode* m_pSibling; }
1.复制原始链表的每一个结点，并用m_pNext链接；设置每一个结点的m_pSibling指针。但该指针可能指向此结点的前面或后面，需从头定位。时间复杂度为O(n^2)
2.哈希表存着配对信息，O(n)
3.
//将原始结点N创建对应的N'。这一次，把N'连接到N的后面 void CloneNodes(ComplexListNode* pHead) { ComplexListNode* pNode=pHead; while(pNode!=NULL){ ComplexListNode* pCloned=new ComplexListNode(); pCloned->m_nValue=pNode->m_nValue; pCloned->m_pNext=pNode->m_pNext; pCloned->m_pSibling=NULL; pNode->m_pNext=pCloned; pNode=pCloned->m_pNext; } } //设置复制出来的结点的m_pSibling void ConnectSiblingNodes(ComplexListNode* pHead) { ComplexListNode* pNode=pHead; while(pNode!=NULL) { ComplexListNode* pCloned=pNode->m_pNext; if(pNdoe->m_pSibling!=NULL) { pCloned->m_pSibling=pNode->m_pSibling->m_pNext; } pNode=pCloned->m_pNext; } } //将长链表拆分成两个链表 ComplexListNode* ReconnectNodes(ComplexListNode* pHead) { ComplexListNode* pNode=pHead; ComplexListNode* pClonedNode=NULL; ComplexListNode* pClonedHead=NULL; if(pNode!=NULL) { pClonedHead=pClonedNode=pNode->m_pNext; pNode->m_pNext=pClonedNode->m_pNext; pNode=pNode->m_pNext; } while(pNode!=NULL) { pClonedNode->m_pNext=pNode->m_pNext; pClonedNode=pClonedNode->m_pNext; pNode->m_pNext=pClonedNode->m_pNext; pNode=pNode->m_pNext; } return pClonedHead; } //总的复制链表的过程 ComplexListNode* Clone(ComplexListNode* pHead) { CloneNodes(pHead); ConnectSiblingNodes(pHead); return ReconnectNodes(pHead); }