题目：请实现函数ComplexListNode* Clone(ComplexListNode* pHead),复制一个复杂链表。在复杂链表中，每个结点除了有一个m_pNext指针指向下一个结点外，还有一个m_pSibling指向链表中的任意结点或者NULL。结点的C++定义如下：

struct ComplexListNode{    int m_nValue;    ComplexListNode* m_pNext;    ComplexListNode* m+pSibling;};

分析：下面方法可以在不用辅助空间的情况下实现O(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(pNode->m_pSibling!=NULL)        {            pCloned->m_pSibling=pNode->m_pSibling->m_pNext;        }        pNode=pCloned->m_pNext;   }}

第三步：把这个长链表分成两个链表，把奇数位置的结点用m_pNext链接起来就是原始链表，把偶数位置的结点用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){    ClonedNodes(pHead);    ConnectSiblingNodes(pHead);    return ReconnectNodes(pHead);}