复杂链表的复制

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

请完成函数ComplexNode* Clone(ComplexNode* pHead)，以复制一个复杂链表。

分析：在常见的数据结构上稍加变化，这是一种很新颖的面试题。要在不到一个小时的时间里解决这种类型的题目，我们需要较快的反应能力，对数据结构透彻的理解以及扎实的编程功底。

看到这个问题，我的第一反应是分成两步：第一步是复制原始链表上的每个链表，并用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²)。

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

第二种方法相当于用空间换时间，以O(n)的空间消耗实现了O(n)的时间效率。

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

/************************************************************************/
/* 复杂链表的复制
题目：有一个复杂链表，其结点除了有一个m_pNext指针指向下一个结点外，
还有一个m_pSibling指向链表中的任一结点或者NULL。其结点的C++定义如下：
struct ComplexNode
{
int m_nValue;
ComplexNode* m_pNext;
ComplexNode* m_pSibling;
};
程序测试链表为:1 2 3 4 5 6; 1的m_pSibling指向4,2的m_pSibling指向5，3的m_pSibling指向6*/
/************************************************************************/


#include<iostream>
#include<malloc.h>
#include<stdlib.h>
#define ERROR 0
using namespace std;

struct _LinkList//链表结构
{
int m_nValue;
_LinkList *m_pNext;
_LinkList *m_pSibling;
};

class CList//链表类
{
private:
_LinkList *List;
public:
CList();
~CList();
void InitList();
void Output();
void CopyList();
};
CList::CList()
{
List=(_LinkList*)malloc(sizeof(_LinkList));
if(!List)
exit(ERROR);
List->m_pNext=NULL;
List->m_pSibling=NULL;
}
CList::~CList()
{

}
void CList::InitList()//初始化链表
{
int data;
_LinkList *head=List;
while(1)
{
cin>>data;
if(data==0)break;
_LinkList *newNode=(_LinkList*)malloc(sizeof(_LinkList));
if(!newNode)
exit(ERROR);
newNode->m_nValue=data;
newNode->m_pNext=NULL;

head->m_pNext=newNode;
head=newNode;
head->m_pNext=NULL;
}
head=List->m_pNext;

while(head)//给链表构造m_pSibling，m_pSibling指向head的后两个结点
{
if(head->m_pNext&&head->m_pNext->m_pNext&&head->m_pNext->m_pNext->m_pNext)
{
_LinkList *temp=head->m_pNext->m_pNext->m_pNext;
head->m_pSibling=temp;
}
else
{
head->m_pSibling=NULL;

}
head=head->m_pNext;

}
}
void CList::Output()//输出链表
{
_LinkList *p,*q;
p=List->m_pNext;
q=List->m_pNext;
while(p)//输出m_pNext的值
{
cout<<" "<<p->m_nValue;
p=p->m_pNext;
}
cout<<endl;
while(q)//输出m_pSibling的值
{
if(q->m_pSibling)
cout<<" "<<q->m_pSibling->m_nValue;
q=q->m_pNext;
}
}
void CList::CopyList()//链表的复制，先在原链表中复制各结点的m_pNext
{
_LinkList *head=List->m_pNext;
_LinkList *cpList=(_LinkList*)malloc(sizeof(_LinkList));
if(!cpList)exit(ERROR);
_LinkList *cphead;//=cpList;

while(head)
{
_LinkList *newNode=(_LinkList*)malloc(sizeof(_LinkList));
if(!newNode)
exit(ERROR);
newNode->m_nValue=head->m_nValue;
newNode->m_pNext=NULL;
newNode->m_pSibling=NULL;

_LinkList *p=head->m_pNext;
head->m_pNext=newNode;
newNode->m_pNext=p;

head=p;
}//复制完成后链表为1 1 2 2 3 3 4 4 5 5 6 6
head=List->m_pNext;
while(head->m_pNext->m_pNext&&head->m_pSibling)//复制各个结点的m_pSibling
{
_LinkList *p=head->m_pNext;
p->m_pSibling=head->m_pSibling->m_pNext;
head=head->m_pNext->m_pNext;
}
head=List->m_pNext;
cphead=head->m_pNext;


while(cphead->m_pNext)//将偶数结点连接起来
{
_LinkList *p=cphead->m_pNext;
cphead->m_pNext=p->m_pNext;
cphead=p->m_pNext;
p->m_pNext=NULL;
}
List->m_pNext=head->m_pNext;
head=List->m_pNext;
while(head)
{
cout<<" "<<head->m_nValue<<endl;;
head=head->m_pNext;
}
}
int main()
{
CList CL=CList();
CL.InitList();
//CL.Output();
cout<<endl;
CL.CopyList();
cout<<"##"<<endl;
CL.Output();
return 1;
}