这题很是巧妙。
突破了常规思维。
竟然可以把传入进来的链表和复制的链表链在一起。然后再算出slibling指针。最后在分离。
直接把空间复杂度变为O(1)了。
很巧妙，很实用。
题目：
请实现函数ComplexListNode* Clone(ComplexListNode* pHead)，复制一个复杂链表。
在复杂链表中，每个结点除了有一个pNext指针指向下一个结点之外，还有一个pSibling指向链表中的任意结点或者NULL。
结点的定义如下：
|
1
2
3
4
5
|
struct ComplexListNode{ int val; ComplexListNode* pNext; ComplexListNode* pSibling;}; |
思路：
方法1：
复制原始链表上的每一个结点，并通过pNext连接起来；然后再设置每个结点的pSibling指针。
假设原始链表中某个结点N的pSibling指针指向结点S,那么就需要从头到尾遍历查找结点S，如果从原始链表的头指针开始，经过m步之后达到结点S，那么在复制链表中的结点N'的pSibling指针指向的结点也是距离复制链表s步的结点。通过这种办法就可以为复制链表上的每个结点设置pSibling指针。
时间复杂度：O(N^2)
方法2：
方法1是通过链表查找来得到pSibling指针所指向的结点，实际上我们可以通过空间换取时间，将原始链表和复制链表的结点通过哈希表对应起来，这样查找的时间就从O(N)变为O(1)。具体如下：
复制原始链表上的每个结点N创建N'，然后把这些创建出来的结点用pNext连接起来。同时把<N,N'>的配对信息方法一个哈希表中；然后设置复制链表中的每个结点的pSibling指针，如果原始链表中结点N的pSibling指向结点S，那么在复制链表中，对应的N'应该指向S'。
时间复杂度：O(N)
方法3：
在不使用辅助空间的情况下实现O(N)的时间效率。
第一步：根据原始链表的每个结点N创建对应的N'，然后将N‘通过pNext接到N的后面；
第二步：设置复制出来的结点的pSibling。假设原始链表上的N的pSibling指向结点S，那么其对应复制出来的N'是N->pNext指向的结点，同样S'也是结点S->pNext指向的结点。
第三步：把长链表拆分成两个链表，把奇数位置的结点用pNext连接起来的就是原始链表，把偶数位置的结点通过pNext连接起来的就是复制链表。