复杂链表的复制

题目：请实现函数 ComplexListNode* Clone(ComplexListNode* pHead)，复制一个复杂链表。在复杂链表中，每个结点除了有一个 m_pNext 指针指向下一个结点，还有一个 m_pSibling 指向链表中的任意结点或者 nullptr。

image.png

一个含有 5 个节点的复杂链表。在复杂链表的节点中，除了有指向下一个节点的指针（实现箭头），还有指向任意节点的指针（虚线箭头）。

---

struct ComplexListNode
{
    int                m_nValue;
    ComplexListNode*    m_pNext;
    ComplexListNode*    m_pSibling;
};

1. 复制复杂链表的第一步

image.png

复制原始链表的任意节点 N 并创建新节点 N'，再把 N' 链接到 N 的后面。

void CloneNodes(ComplexListNode* pHead)
{
    ComplexListNode* pNode = pHead;
    while(pNode != nullptr)
    {
        ComplexListNode* pCloned = new ComplexListNode();
        pCloned->m_nValue = pNode->m_nValue;
        pCloned->m_pNext = pNode->m_pNext;
        pCloned->m_pSibling = nullptr;
 
        pNode->m_pNext = pCloned;
 
        pNode = pCloned->m_pNext;
    }
}

2. 复制复杂链表的第二步

image.png

设置复制出来的节点的 m_pSibling。假设原始链表上的 N 的 m_pSibling 指向节点 S，那么其对应复制出来的 N' 是 N 的 m_pNext 指向的节点，同样 S' 也是 S 的 m_pNext 指向的节点。

如果原始链表上的节点 N 的 m_pSibling 指向 S，则它对应的复制节点 N' 的 m_pSibling 指向 S 的复制节点 S'。

void ConnectSiblingNodes(ComplexListNode* pHead)
{
    ComplexListNode* pNode = pHead;
    while(pNode != nullptr)
    {
        ComplexListNode* pCloned = pNode->m_pNext;
        if(pNode->m_pSibling != nullptr)
        {
            pCloned->m_pSibling = pNode->m_pSibling->m_pNext;
        }
 
        pNode = pCloned->m_pNext;
    }
}

3. 复制复杂链表的第三步

image.png

把这个长链表拆分成两个链表：把奇数位置的节点用 m_pNext 链接起来就是原始链表，把偶数位置的节点用 m_pNext 链接起来就是复制出来的链表。

ComplexListNode* ReconnectNodes(ComplexListNode* pHead)
{
    ComplexListNode* pNode = pHead;
    ComplexListNode* pClonedHead = nullptr;
    ComplexListNode* pClonedNode = nullptr;
 
    if(pNode != nullptr)
    {
        pClonedHead = pClonedNode = pNode->m_pNext;
        pNode->m_pNext = pClonedNode->m_pNext;
        pNode = pNode->m_pNext;
    }
 
    while(pNode != nullptr)
    {
        pClonedNode->m_pNext = pNode->m_pNext;
        pClonedNode = pClonedNode->m_pNext;
 
        pNode->m_pNext = pClonedNode->m_pNext;
        pNode = pNode->m_pNext;
    }
 
    return pClonedHead;
}

4. 把上面三步合起来，就是复制链表的完整过程。

ComplexListNode* Clone(ComplexListNode* pHead)
{
    CloneNodes(pHead);
    ConnectSiblingNodes(pHead);
    return ReconnectNodes(pHead);
}

摘抄资料：《剑指offer》