所謂復雜鏈表就是含有一個任意指向的指針的鏈表
1.png
//復制復雜的鏈表
//solution1:
struct listNode
{
int data;
listNode* pnext;
listNode* psibling;
};
關于復制鏈表氛改，由于這里多了一個“隨意”的指針目尖，處理這個比較麻煩。
思路1：先復制pnext節(jié)點寺晌，然后遍歷查找psibling。
這樣做復雜度太高澡刹，O(N2)
思路2：將原先鏈表中psibling指向的節(jié)點N和復制后產生的節(jié)點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);
}
文章參考何海濤大神文章
