复杂链表的复制

题目描述：给定一个复杂链表，该链表的节点除了包含指向下一个节点的指针，还包括一个指向链表中任意节点的指针。要求：将该链表复制一份并返回复制链表的头节点指针

复杂链表节点的定义如下：

struct ComplexListNode
{
    int value;
    ComplexListNode *pNext;
    ComplexListNode *pSibling;
};

题目分析：该复杂链表相比于常见的普通链表的节点多了一个指向任意链表节点的指针，因此我们可以考虑在复制的时候先将原链表复制一份，然后再将pSibling指针不为空的节点的pSibling指针赋值给复制链表的节点，这种实现方式的时间复杂度为O(n)，空间复杂度为O(n)。其实现代码如下：

#include<iostream>
#include<vector>
using namespace std;

struct ComplexListNode
{
    int value;
    ComplexListNode *pNext;
    ComplexListNode *pSibling;
};
//使用辅助空间复制链表
ComplexListNode *copyComplexList(ComplexListNode *pHead)
{
    if (pHead == nullptr){ return 0; }
    //新建一个ComplexNode作为复制链表的头节点
    ComplexListNode *pCopyHead = new ComplexListNode;
    pCopyHead = pHead;
    vector<ComplexListNode *>Sibling;//用来保存Sibling不为空的节点
    pCopyHead->value = pHead->value;
    pCopyHead->pNext = pHead->pNext;
    //这一步将Sibling指针成员不为空的节点保存下来
    if (pHead->pSibling != nullptr){ Sibling.push_back(pHead); }

    ComplexListNode *pNode = pHead->pNext;
    while (pNode!=nullptr)
    {
        //新建立一个ComplexNode作为复制链表的节点
        ComplexListNode *pListNext = new ComplexListNode;
        pListNext = pNode;
        pListNext->value = pNode->value;
        pListNext->pNext = pNode->pNext;
        if (pNode->pSibling != nullptr){ Sibling.push_back(pNode); }
        else{ pListNext->pSibling = pNode->pSibling; }
        pNode = pNode->pNext;
    }
    
    if (Sibling.size()>0)
    {
        ComplexListNode *pNodeHasSibling = nullptr;
        ComplexListNode *tmpNode = pCopyHead;
        vector<ComplexListNode*>::iterator iter = Sibling.begin();
        //逐个将Sibling容器里存放的节点的Sibling指针成员赋给复制链表里相应的节点
        for (; iter != Sibling.end(); iter++)
        {
            pNodeHasSibling = *iter;
            while (pNodeHasSibling!=tmpNode)
            {
                tmpNode = tmpNode->pNext;
            }
            tmpNode->pSibling = (*iter)->pSibling;
        }
    }
    return pCopyHead;
}

如果没有额外的辅助空间，我们应该如何解决这个问题呢？我们可以在原链表的基础上进行实现，具体思路如下：

1、在原链表中将每个节点复制一次并插入到原链表中每一个节点之后，Sibling指针成员不复制，因为Sibling指向的节点可能位于当前节点的后面；

2、将原链表节点的Sibling指针指向的节点赋给复制节点的Sibling指针；
3、将复制节点逐个连接起来，并返回复制节点的头指针；
将这三个部分分别用函数实现，实现代码如下：

#include<iostream>
using namespace std;

struct ComplexListNode
{
    int value;
    ComplexListNode *pNext;
    ComplexListNode *pSibling;
};

void cloneNodes(ComplexListNode *pHead)
{
    if (pHead == nullptr){ return; }
    ComplexListNode *pNode = pHead;
    while (pNode!=nullptr)
    {
        ComplexListNode *pClonedNode = new ComplexListNode;
        pClonedNode->value = pNode->value;
        pClonedNode->pNext = pNode->pNext;
        pClonedNode->pSibling = nullptr;

        pNode->pNext = pClonedNode;
        pNode = pClonedNode->pNext;
    }
}

//给新复制的节点的Sibling指针成员赋值
void ConnectSiblingNodes(ComplexListNode *pHead)
{
    if (pHead == nullptr){ return; }
    ComplexListNode *pNode = pHead;
    while (pNode != nullptr)
    {
        ComplexListNode *pCloned = pNode->pNext;
        if (pNode->pSibling != nullptr)
        {
            pCloned->pSibling = pNode->pSibling->pNext;
        }
        pNode = pCloned->pNext;
    }
}


//将新复制的节点连接起来
ComplexListNode *ReconnectNodes(ComplexListNode *pHead)
{
    ComplexListNode *pNode = pHead;
    ComplexListNode *pClonedHead = nullptr;
    ComplexListNode *pClonedNode = nullptr;

    if (pNode != nullptr)
    {
        pClonedHead = pClonedNode = pNode->pNext;
        pNode->pNext = pClonedNode->pNext;
        pNode = pClonedNode->pNext;
    }

    while (pNode!=nullptr)
    {
        //将pClonedNode的pNext指向当前原链表节点的下一个节点
        pClonedNode->pNext = pNode->pNext;
        //将pClonedNode置为原链表节点的下一个节点
        pClonedNode = pClonedNode->pNext;
        //将原链表节点的pNext指向pClonedNode的下一个节点，否则原链表就断开了
        pNode->pNext = pClonedNode->pNext;
        //将原链表节点后移
        pNode = pNode->pNext;
    }
    return pClonedHead;
}

//总体的复制函数
ComplexListNode *Clone(ComplexListNode *pHead)
{
    cloneNodes(pHead);
    ConnectSiblingNodes(pHead);
    return ReconnectNodes(pHead);
}

上述就是这个问题的两种典型解决办法了，当然还有一种实现方法：在复制每一个链表节点的同时去找到它的Sibling指针指向的节点，然后将复制节点的Sibling指针也指向它。但是这种办法的时间复杂度为O(n^2)，这里不推荐这种方法，因此没有给出具体实现的代码。