题目：有一个复杂链表，其结点除了有一个指针指向下一个结点外，还有一个指向链表中的任一结点或者NULL。请完成函数 Clone( pHead)，以复制一个复杂链表。其结点的C++定义如下：

  struct

  {

  int ;

  * ;

  * ;

  };

  下图是一个含有5个结点的该类型复杂链表。图中实线箭头表示指针，虚线箭头表示指针。为简单起见，指向NULL的指针没有画出。

  方法一：看到这个问题，我的第一反应是分成两步：第一步是复制原始链表上的每个链表，并用链接起来；第二步，假设原始链表中的某节点N的指向结点S，由于S的位置在链表上有可能在N的前面也可能在N的后面，所以要定位N的位置需要从原始链表的头结点开始找，假设从原始链表的头结点开始经过s步找到结点S复杂链表的复制，那么在复制链表上结点N的的S’，离复制链表的头结点的距离也是s，用这种办法我们就能为复制链表上的每个结点设置了。对含有n个结点的链表，由于定位每个结点的都需要从链表头结点开始经过O(n)步才能找到，因此这种方法的总时间复杂度是O(n2)。

  方法二：换一种思路，在不用新关键词空间的情况下实现O(n)的时间效率。第三种方法的第一步仍然是根据原始链表的每个结点N，创建对应的N’。这一次，我们把N’链接在N的后面。实例中的链表经过这一步之后变成了：

void CloneNodes(ComplexNode* pHead)
{
ComplexNode* pNode=pHead;
![c语言单链表复制_复杂链表的复制_复杂句 复杂句 区别][1] while(pNode!=NULL) { ComplexNode* pCloned=new ComplexNode(); pCloned->m_nValue=pNode->m_nValue; pCloned->m_pNext=pNode->m_pNext; pCloned->m_pSibling=NULL; pNode->m_pNext=pCloned; pNode=pCloned->m_pNext; } }

  第二步是设置我们复制出来的链表上的结点的。假设原始链表上的N的指向结点S复杂链表的复制，那么其对应复制出来的N’是N->，同样S’也是S->。这就是我们在上一步中把每个结点复制出来的结点链接在原始结点后面的原因。有了这样的链接方式，我们就能在O(1)中就能找到每个结点的了。例子中的链表经过这一步，就变成如下结构了：

void ConnectSiblingNodes(ComplexNode* pHead)
{
ComplexNode* pNode=pHead;
while(pNode)
{
    ComplexNode* pCloned=pNode->m_pNext;
    if(pNode->m_pSibling)
        pCloned->m_pSibling=pNode->m_pSibling->m_pNext;
    pNode=pCloned->m_pNext;
![复杂链表的复制_复杂句 复杂句 区别_c语言单链表复制][3] } }

  第三步是把这个长链表拆分成两个：一个原始链表，还有一个就是我们复制的链表了。

ComplexNode ReconnectNodes(ComplexNode pHead)
{
ComplexNode* pNode=pHead;
ComplexNode* pClonedHead=NULL;
ComplexNode* pClonedNode=NULL;
if(pNode!=NULL)
![复杂链表的复制_复杂句 复杂句 区别_c语言单链表复制][4] { 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;   ![复杂链表的复制_c语言单链表复制_复杂句 复杂句 区别][5] pNode->m_pNext=pClonedNode->m_pNext; pNode=pNode->m_pNext; } return pClonedHead; }

  把上面三步合起来，就是复制链表的完整过程：

ComplexNode Clone(ComplexNode pHead)
{
CloneNodes(pHead);
ConnectSiblingNodes(pHead);
ReconnectNodes(pHead);
}