//复制复杂链表
#include <iostream>

using namespace std;
struct ComplexListNode{
    int m_nValue;
    ComplexListNode* m_pNext;
    ComplexListNode* m_pSibling;
};
void Insert(ComplexListNode* &pHead,int data){
    ComplexListNode* pNode=new ComplexListNode();
    pNode->m_nValue=data;
    pNode->m_pNext=NULL;
    pNode->m_pSibling=NULL;
    if(pHead==NULL)
        pHead=pNode;
    else{
        pNode->m_pNext=pHead;
        pHead=pNode;
    }
}
void Print(ComplexListNode* &pHead){
    if(pHead==NULL)
        return;
    ComplexListNode* pNode=pHead;
    while(pNode){
        cout<<pNode->m_nValue<<" ";
        pNode=pNode->m_pNext;
    }
    cout<<endl;
}
//第一步复制各个节点，并形成链表
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;//插入Cloned节点
        pNode=pCloned->m_pNext;   //依次往后挪
    }
}
//复制原来节点m_pSibling指针的指向情况
void ConnectSiblingNodes(ComplexListNode* pHead){
    ComplexListNode* pNode=pHead;
    while(pNode!=NULL){
        ComplexListNode* pCloned=pNode->m_pNext;
        if(pNode->m_pSibling!=NULL)
                pCloned->m_pSibling=pNode->m_pSibling->m_pNext;
        pNode=pCloned->m_pNext;
    }
}
//按照奇偶位置拆分原始链表和复制链表
ComplexListNode* ReconnectNodes(ComplexListNode* pHead){
    ComplexListNode* pNode=pHead;
    ComplexListNode* pClonedHead=NULL;
    ComplexListNode* pClonedNode=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);
}
int main()
{
    ComplexListNode* l=NULL;
    ComplexListNode* c=NULL;
    Insert(l,1);
    Insert(l,2);
    Insert(l,3);
    Insert(l,4);
    Insert(l,5);
    Print(l);

    c=Clone(l);
    Print(c);
    return 0;
}