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

struct ComplexListNode
{
int m_nValue;
ComplexListNode* m_pNext;
ComplexListNode* m_pSibling;
};

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

在常见的数据结构上稍加变化，这是一种很新颖的面试题。看到这个问题，我的第一反应是分成两步：第一步是复制原始链表上的每个结点，并用m_pNext链接起来；第二步，假设原始链表中的某节点N的m_pSibling指向结点S。由于S的位置有可能在N的前面也可能在N的后面，所以要定位N的位置需要从原始链表的头结点开始找。假设从原始链表的头结点开始经过s步找到结点S。那么在复制后的链表上结点N’的m_pSibling(记为S’)，离头结点的距离也是s。用这种办法就能为复制后的链表的每个结点设置m_pSibling了。

对一个含有n个结点的链表，由于定位每个结点的m_pSibling都需要从链表头结点开始经过O(n)步才能找到，因此这种方法的总时间复杂度是O(n^2)。

由于上述方法的时间主要花在定位结点的m_pSibling上面，我们试着在这方面做优化。还是分两步：第一步仍然是复制原始链表上的每个结点N，并创建N’，然后把这些创建出来的结点链接起来。同时我们把<N, N’>的配对信息放到一个哈希表中。第二步还是设置复制后的链表上每个结点的m_pSibling。如果在原始链表中结点N的m_pSibling指向结点S，那么在复制后的链表中，对应的N’应该指向S’。由于有了哈希表，可以用O(1)的时间根据S找到S’。这种方法相当于用空间换时间，以O(n)的空间消耗把时间复杂度由O(n^2)降低到O(n)。

(注：哈希表中的每一个配对(pair)的Key是原始链表的结点，Value是Key中结点的对应的拷贝结点。这样在哈希表中，就可以在O(1)的时间里，找到原始结点对应的拷贝出来的结点。比如想求得N’的m_pSibling所指向的S’，可以由N的m_pSibling求得S，而<S, S’>的配对信息就在哈希表中，可以用O(1)时间求得。)

在解决复杂问题时，可以将复杂问题分成多个步骤的小问题。然后每一步解决一个小问题，各个击破，这样整个过程的逻辑也会更加清晰明了。计算机中常用的一类算法“分治法”，也是基于这个思想。

下面换一种思路来解决这个问题，在不用辅助空间的情况下实现O(n)的时间效率。第三种方法的第一步仍然是根据原始链表的每个结点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。假设原始链表上的N的m_pSibling指向结点S，而N对应的复制出来的N’等于N->m_pNext，同样S’就等于S->m_pNext。这就是在上一步中把每个复制出来的结点链接在原始结点后面的原因。有了这样的链接方式，就能在O(1)时间中找到每个结点的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;
}

（注：while循环的前两行代码是设置完“复制后的链表”的当前结点的m_pNext之后，将指针pClonedNode后移。后两行代码是设置完“原始链表” 的当前结点的m_pNext之后，将指针pNode后移。以便继续处理，如果一时理解不了，就动笔划一划。）

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