所谓复杂链表就是含有一个任意指向的指针的链表
1.png
//复制复杂的链表
//solution1:
struct listNode
{
int data;
listNode* pnext;
listNode* psibling;
};
关于复制链表，由于这里多了一个“随意”的指针，处理这个比较麻烦。
思路1：先复制pnext节点，然后遍历查找psibling。
这样做复杂度太高，O(N2)
思路2：将原先链表中psibling指向的节点N和复制后产生的节点N'存放在一个hash表里面，这样就可以直接找到N’了
思路3：
solution3
先复制pnext，再连接psibling，然后重新组织。
复制pnext：
//first copy the nodes
//a-a'-b-b'-c-c'-...
void copynodes(listNode* l)
{
if (!l)
return;
listNode* phead = l;
while (phead->pnext)
{
listNode* cp = new listNode;
cp->data = phead->data;
cp->pnext = phead->pnext;
phead->pnext = cp;
phead = cp->pnext;
}
}
再复制psibling：
//copy siblings
void copySibling(listNode* l)
{
if (!l)
return;
listNode* phead = l;
while (phead)
{
while (phead->psibling)
{
phead->pnext->psibling = phead->psibling->pnext;
}
phead = phead->pnext->pnext;
}
}
再分离&重新连接：
//seperate
listNode* reconnect(listNode* l)
{
listNode* cloneNode=NULL;
listNode* cloneHead=NULL;
listNode* phead = l;
if (phead != NULL)
{
cloneHead = cloneNode = phead->pnext;
phead->pnext = cloneNode->pnext;
phead = phead->pnext;
}
while (phead)
{
cloneNode->pnext = phead->pnext;
cloneNode = cloneNode->pnext;
phead->pnext = cloneNode->pnext;
phead = phead->pnext;
}
return cloneHead;
}
驱动程序：
listNode* clone(listNode* l)
{
copynodes(l);
copySibling(l);
return reconnect(l);
}
文章参考何海涛大神文章
