复制复杂链表（1）

所谓复杂链表就是含有一个任意指向的指针的链表

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);
}

文章参考何海涛大神文章