面试题26:复杂链表的复制

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

struct ComplexListNode{

    int m_nValue;

    ComplexListNode* m_pNext;

    ComplexListNode* m_pSibling;

};

思路1：第一步复制原始链表上的每个结点N创建N‘，然后把这些创建出来的结点用m_pNext链接起来。同时把<N, N'>的配对信息放到一个哈希表中。第二步还是设置复制链表上每个结点的m_pSibling。如果在原始链表中结点N的m_pSibling指向结点S，那么中复制链表中，对于的N'应该指向S'。

思路2:在不用辅助空间的情况下实现O(n)的时间效率。第三种方法的第一步仍然是根据原始链表的每个结点N创建对应的N'。把N'链接在N后面。第二步设置复制出来的结点的m_pSibling.假设原始链表上的N的m_pSibling指向结点S，那么其对应复制出来的N'是N的m_pNext指向的结点，同样S'也是S的m_pNext指向的结点。第三步就是把这个长链表拆分成两个链表：把奇数位置的结点用m_pNext链接起来就是原始链表，把偶数位置的结点用m_pNext链接起来就是复制出来的链表。